0

For some $x \in N$ and $n \in N$, suppose $0 \leq a_i < x$ and $0 \leq b_i < x$ for $i=0,...,n-1$ and that the following is true

$$ \sum_{i=0}^{n}a_i\cdot x^i = \sum_{i=0}^{n}b_i\cdot x^i $$

How can we show that $a_i\cdot x^i$ = $b_i\cdot x^i$ for all $i$, and more specifically, that $a_i = b_i$ for all $i$?

In written terms, how can we show that if $n$ numbers are encoded in base $x$ where each digit is used to hold a single number (each number is less than $x$), that two equal encodings imply that each number used to obtain one encoding is the same as the corresponding number used to obtain the other encoding?

Essentially I am trying to show that the encoding is a bijection.

David Callanan
  • 395
  • 1
    what does "for some $x \in \mathbb N$" mean? If it is for just one value (e.g. $x = 1$) then it isn't true. If it holds for arbitrary $x \in \mathbb N$ then it follows e.g. by using a Vandermonde Matrix or arguing that non-constant polynomial of degree $\leq n$ polynomial has at most $n$ roots but your polynomial has $\infty$ roots. – user8675309 Mar 06 '22 at 22:11

1 Answers1

1

You would also require that $a_i, b_i \in \mathbb N$.

Suppose $\sum_{i=0}^n a_i x^i = \sum_{i=0}^n b_ix^i$, then

$$ (b_n - a_n)x^n = \sum_{i=0}^{n-1} (a_i-b_i)x^i $$

Note that $|a_i - b_i| \leq x-1$, so

$$ |a_n - b_n|x^n \leq (x-1)\sum_{i=0}^{n-1} x^i = x^n - 1$$

which is impossible if $|a_n-b_n| \geq 1$, thus $a_n - b_n = 0$.

Having established $a_n = b_n$, you have $\sum_{i=0}^{n-1} a_i x^i = \sum_{i=0}^{n-1} b_ix^i$, and can apply the same argument to show $a_{n-1} = b_{n-1}$, etc.

messenger
  • 1,026