Prove by induction that $r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n$.

Question

Let $a$ be a natural number greater than $1$. Prove that for all integers $r_0 , r_1 , \cdots , r_{n−1}$ with $0 ≤ r_j < a$, we have: $$ r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} < a^n $$

I am unable to prove the induction step.

Answer 1

If you're required to use induction:

If the statement is true for $n=k$, then we have \begin{align*} r_0 + r_1a + \dots + r_{n-1}a^{n-1} + r_na^n &< a^n + r_na^n = (1+r_n)a^n. \end{align*} Now, if $r_n$ is an integer strictly less than $a$, then $r_n \leq a-1$, so ...

Answer 2

Notice that since $a$ and each $r_j$ are integers, we know that: $$ r_j < a \implies 1 + r_j \leq a \tag{$\star$} $$ Now the induction step is easy: \begin{align*} r_0 + r_1a + r_2a^2 + \cdots + r_{n−1}a^{n−1} &< a^{n-1} + r_{n-1}a^{n-1} &\text{by the induction hypothesis} \\ &= (1 + r_{n-1})a^{n-1} \\ &\leq (a)a^{n-1} &\text{by }(\star) \\ &= a^n \end{align*} as desired.