Showing that every positive integer can be represented in this form How can we prove that for every pair $N \in \mathbb{N}$, and natural number $\beta\in [2, \infty)$ there exists a unique set of integers $x_i \in [0, \beta -1]$, $k\in [0,\infty)$ such that:
$$N = \sum_{i=0}^{k}\beta^ix_{i}, \quad $$
It's a question if every positive integer has its unique representation in every base $\beta$.
Is the validity of above statement somehow related to Horner's rule?
 A: Existence.
The existence involves the division algorithm: write
\begin{align}
N=N_0&=\beta N_1+x_0 &&0\le x_0<\beta\\
N_1&=\beta N_2+x_1 &&0\le x_1<\beta\\
&\,\vdots\\
N_k&=\beta N_{k+1}+x_k &&0\le x_k<\beta
\end{align}
stopping when $N_{k+1}=0$ (that is, $N_k<\beta$). Note that $x_k\ne0$ by construction, unless $N=0$.
Since $N=N_0>N_1>\dotsb$, the algorithm terminates. This proves existence.
Indeed, rereading the steps we have
\begin{align}
N&=x_0+\beta N_1\\
&=x_0+\beta(x_1+\beta N_2)=x_0+\beta x_1+\beta^2 N_2\\
&\,\vdots\\
&=x_0+\beta x_1+\dots+\beta^{k-1}(x_{k-1}+\beta N_k)\\
&=x_0+\beta x_1+\dots+\beta^{k-1}x_{k-1}+\beta^k x_k
\end{align}
A more formal proof is by induction on the number of steps, noting that the algorithm for $M=(N-x_0)/\beta$ requires one step less than the algorithm for $M$
and requires the same computations done for $N$. Let's make it more precise.
Base of the induction. If the algorithm stops at step $0$, then $N=x_0$.
Induction step. Suppose the algorithm for $N$ stops at step $k>0$. Set $M=(N-x_0)/\beta$ which is integer by construction. Then, setting $M_{i}=N_{i+1}$ and $y_i=x_{i+1}$ for $i=0,1,\dots, k-1$, we have
\begin{align}
M=M_0&=\beta N_1+y_0 &&0\le y_0<\beta\\
M_1&=\beta M_2+y_1 &&0\le y_1<\beta\\
&\,\vdots\\
M_{k-1}&=\beta M_{k}+y_{k-1} &&0\le y_{k-1}<\beta
\end{align}
and $M_{k-1}<\beta$, so the algorithm stops in $k-1$ steps. By the induction hypothesis we have
$$
M=y_0+\beta y_1+\dots+\beta^{k-1}y_{k-1}
$$
so, substituting back,
$$
N=x_0+\beta(x_1+\beta x_2+\dots+\beta^{k-1}x_k)
=x_0+\beta x_1+\beta^2 x_2+\dots+\beta^k x_k
$$
Uniqueness.
By contradiction, suppose $N$ is the least integer admitting two representations, say
$$
N=\sum_{i=0}^k \beta^i x_i=\sum_{i=0}^h \beta^i y_i.
$$
Prove that $N>\beta$. Then
$$
N=x_0+\beta\biggl(\sum_{i=1}^k\beta^{i-1}x_i\biggr)
=y_0+\beta\biggl(\sum_{i=1}^h\beta^{i-1}y_i\biggr)
$$
with $0\le x_0<\beta$ and $0\le y_9<\beta$. By the uniqueness of the remainder under division by $\beta$, we have $x_0=y_0$. Then set
$$
M=\sum_{i=1}^k\beta^{i-1}x_i=\sum_{i=1}^h\beta^{i-1}y_i.
$$
Now $M<N$, so it has a unique representation; therefore $h=k$ and $x_i=y_i$ for $i=1,2,\dots,k$. Contradiction.
I don't think uniqueness can be proved “constructively”, but the argument by contradiction above is just a form of induction: prove that if all numbers less than $N$ have a unique representation, then also $N+1$ has a unique representation.
