Proving the divisibility $a-1\mid a^n-1$ using induction

Question

Question:

Let $a$ be an integer different than $1$. Prove by induction, that for any $n \in\Bbb N$, $ a^n -1$ is divisible by $a-1$.

My attempt:

Base Case is trivial.

I.H: Assume $ a^k -1$ is divisible by $a-1$, $k \in N$

Then,

$$ a^{k+1} -1 = a\cdot a^k -1 + a^k -1 - a^k + 1 = a\cdot a^k - a^k + a^k -1 = (a^k)(a-1) + (a^k -1)$$which is divisible by $ a-1$.

Hence, proven by induction.

Is this the correct way to prove it using induction? Is there a more efficient way to prove it using induction?

Answer 1

Let $a>1$ be an integer. Prove by induction that for any $n \in \mathbb{N}$, $ a^n -1$ is divisible by $a-1$.

$\textbf{Proof}.$ Base case: let $n=1$. Then it is clear that $a-1|a-1$.

Induction hypothesis: assume that $a-1|a^k-1$ for some integer $k$. Consider $a^{k+1}-1$, which could be rewritten as $$ \begin{align*} a^{k+1}-1 &= a\cdot a^k + a^k-a^k-1 \\ &= a^k(a-1)+ (a^k-1). \\ \end{align*} $$ Since $a-1|a^k(a-1)$ and $a-1|a^k-1$ by the induction hypothesis, $a-1|a^{k+1}-1$.

Thus $a-1|a^n-1$.

Answer 2

Hint $\ $ The inductive step follows by telescopy. $ $ Let $f(k)= a^k-1$

Then $\,\color{#0a0}{f(k\!+\!1)\!-\!f(k)} = a^{k+1}-a^k = (a\!-\!1)a^k$ is divisible by $\,a\!-\!1$

so if $\,\color{#c00}{f(k)}$ is divisible by $\,a\!-\!1\,$ then so too is $\,f(k\!+\!1) = \color{#0a0}{f(k+1)\!-\!f(k)} + \color{#c00}{f(k)}$

Remark $\, $ Summing the above makes the telescopic cancellation explicit

$$\begin{align}a^{k+1}-1 =\, &\,\ \ \color{#c00}{a^{k+1}\!-a^k}+\color{#0a0}{a^k\!-a^{k-1}} + \cdots+ a^1\!-a^0\\[.3em] =\, &\,(a-1)\, (\color{#c00}{a^k} + \color{#0a0}{a^{k-1}}+\cdots+1),\ \ \text{or, more formally}\\ f(k\!+\!1)-f(0) =\,& \sum_{i=0}^k (f(i\!+\!1)\!-\!f(i)) = \sum_{i=0}^ka^i(a\!-\!1) = (a\!-\!1)\sum_{i=0}^k a^i\end{align} $$

The first equality above, expressing $f(k\!+\!1)-f(0)$ as the sum of its first differences, has a trivial (and obvious) proof by induction. Once you prove this general form inductively, you can use it as a lemma to inductively prove many special cases - which are ubiquitous. You can find many examples and much further discussion of telescopic induction in various prior posts.