Proof of Basis Representation Theorem
I am studying Number Theory from Andrews's Number Theory book. This theorem has been proved in the book but I'm wondering if my proof is correct.
(Basis Representation Theorem) Let $k$ be an integer greater than 1. Then, for each positive integer $n$, there exists a representation$$n=a_0k^s+a_1k^{s-1}+\ldots + a_s$$ where $a_0 \ne 0$, and where each$a_i$ is nonnegative and less than $k$. Furthermore, this representation of $n$ is unique; it is called the representation of$n$ to the base $k$.
Here's my attempt:
Let $k \in \mathbb{N}$ be given. We do the proof by induction on $n$. Base case is easy to check: $1 = 1 \cdot k^{0}$. Suppose the statement is true for $n\in \mathbb{N}$. Now, we show that the statement holds for $n+1$ as well.
By the induction hypothesis, there exists $a_0, \ldots , a_s \in \mathbb{Z}_{\ge 0}$, $a_0 \ne 0$, each of which is less than $k$, such that $n=a_0k^s+a_1k^{s-1}+\ldots + a_s$. Now, we consider$$n+1=a_0k^s+a_1k^{s-1}+\ldots + (a_s+1)$$Since $a_s <k$, we have then that $a_s+1 \le k$. If $a_s+1 < k$, then we are done. If not, we have that $a_s +1=k$ and hence $n+1=a_0k^s + a_1k^{s-1}+\ldots + (a_{s-1}+1)k$. Again, we have that $(a_{s-1}+1) \le k$. If $a_{s-1}+1<k$ then we are done. If not then $a_{s-1}+1=k$ then we have $n+1=a_0k^s + a_1k^{s-1}+\ldots + (a_{s-2}+1)k^2$. Repeating this, we either have that $a_{s}+1=k, a_{s-i}+1=k, \ldots, a_{s-i}+1<k$ for some $i <s$ or $a_{s-i}+1=k$ for all $i \le s$. In the former case, we would have proven our claim. In latter case, we have$$n=(k-1)(k^{s}+k^{s-1}+\ldots + 1) = k^{s+1}-1$$and hence $n+1=k^{s+1}$ and we are done.
For the uniqueness part, suppose that$$n=a_0k^s+a_1k^{s-1}+\ldots + a_s$$and$$n=a_0'k^s+a_1'k^{s-1}+\ldots + a_s'$$. We claim that $a_s=a_s'$. Note that $0\le|a_s-a_s'|<k$ and from the above two equations $k$ divides $|a_s-a_s'|$. Hence, $a_s=a_s'$. Let $i < s$ and suppose that we have shown that $a_s=a_s', a_{s-1}=a_{s-1}', \ldots, a_{s-i}=a_{s-i}'$ . Note that $0\le|a_{s-i-1}-a_{s-i-1}'|<k$ and from the above equation and our assumption, $k$ divides $|a_{s-i-1}-a_{s-i-1}'|$, hence $a_{s-i-1}=a_{s-i-1}'$. Thus, $a_{s-i}=a_{s-i}'$ for all $0\le i \le s$.
This completes the proof. Is my proof correct?
$\endgroup$ 3 Reset to default
