Proving $r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} < a^k$ by INDUCTION.

Question

Let $a$ be a natural number $>1$. For all integers $r_0, r_1, \dots, r_{n-1}$ with $0\leq r_{j} < a$, then \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{n-1}a^{n-1} < a^n. \end{eqnarray}

---

Consider the base case for $n_0=2$. Thus $r_0+r_1a<a^2$, which is not so obviously true, but given that $0\leq r_{j} < a$ and the conditions on both $a$ and the $r_j$'s, then the maximum value that $r_0+r_1a$ can attain is when $r_0=r_1=(a-1)$. Thus, we have

\begin{eqnarray} r_0+r_1a & = & (a-1)+(a-1)a\\ & = & (a-1)(a+1)\\ & = & a^2-1, \end{eqnarray} which clearly suffices to show that the inequality $r_0+r_1a<a^2$ holds, namely $a^2-1<a^2$. Now, let $k$ be some number $>2$. By assumption \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} < a^k, \end{eqnarray} with the same conditions as are listed in the theorem above. However, we must show that \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1}+r_ka^k < a^{k+1}. \end{eqnarray} To continue, let us add $r_ka^k$ to both sides of the inequality we made by assumption: \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1}+r_ka^k & < & a^k+r_ka^k\\ & = & a^k(r_k+1)\cdots \text{Where to now? :-(} \end{eqnarray}

Answer 1

Let $R$ be $\max(r_i)\implies R\le a-1$ as $r_i$s are integers (As Aryabhata commented)

So, $$r_0+r_1a+r_2a^2+\cdots+r_{n-1}a^{n-1}$$ $$\le R\cdot(1+a+a^2+\cdots+a^{n-1})$$ $$\le(a-1)\cdot\left(\frac{a^n-1}{a-1}\right)=a^n-1\text{ as }a\ne1 \text{ as }a>1$$

$$<a^n$$

Answer 2

Consider the base case for $n_0=2$. Thus $r_0+r_1a<a^2$, which is not so obviously true, but given that $0\leq r_{j} < a$ and the conditions on both $a$ and the $r_j$'s, then the maximum value that $r_0+r_1a$ can attain is when $r_0=r_1=(a-1)$. Thus, we have

\begin{eqnarray} r_0+r_1a & = & (a-1)+(a-1)a\\ & = & (a-1)(a+1)\\ & = & a^2-1, \end{eqnarray} which clearly suffices to show that the inequality $r_0+r_1a<a^2$ holds, namely $a^2-1<a^2$. Now, let $k$ be some number $>2$. By assumption \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} < a^k, \end{eqnarray} with the same conditions as are listed in the theorem above. However, we must show that \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1}+r_ka^k < a^{k+1}. \end{eqnarray} To continue, let us subtract $r_ka^k$ from both sides of the inequality above: \begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1} & < & a^{k+1}-r_ka^k\\ & = & a^k(a-r_k). \end{eqnarray} Now, since $r_k<a$, then $(a-r_k)$ is positive and thus $a^k(a-r_k)>a^k$, in particular \begin{eqnarray} {\bf{r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1}<a^k}}<a^k(a-r_k), \end{eqnarray}

for which the bold part we made by assumption. Therefore,

\begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{k-1}a^{k-1}+r_ka^k<a^{k+1} \end{eqnarray}

holds and suffices to attest to the existence of

\begin{eqnarray} r_0+r_1a+r_2a^2+\cdots+r_{n-1}a^{n-1}<a^n \end{eqnarray}

for all $n$.