# Using the second principle of finite induction to prove $a^n -1 = (a-1)(a^{n-1} + a^{n-2} + … + a + 1)$ for all $n \geq 1$

The hint for this problem is $a^{n+1} - 1 = (a + 1)(a^n - 1) - a(a^{n-1} - 1)$

I see that the problem is true because if you distribute the $a$ and the $-1$ the terms cancel out to equal the left side. However, since it is telling me to use strong induction I am guessing there is more I am supposed to be doing. On the hint I can see that it is a true statement, but I am not sure how to use that to prove the equation or how the right side of the hint relates to the right side of the problem. Also, I do realize that in the case of the hint $n = 1$ would be the special case.

-
Hmm, your correction came in 6 seconds after mine! –  Bill Dubuque Dec 23 '10 at 20:45
@Bill Dubuque I was wondering what you meant by correcting it. I thought I had done that. And the book is "Elementary Number Theory" 4th edition by David Burton. Actually the strong induction part is not completely clear to me. The other day I asked a question on what strong induction (or second principle of finite induction as my book puts it) is. The answers were helpful and I think I grasp it a little, but this problem is different then the example problem and I am a little lost on how to proceed. Especially since it seems strong induction is not necessary. –  qw3n Dec 23 '10 at 20:54
To prove for $n+1$, using the hint, you need to assume for $n-1$ and $n$, so it is using strong induction. –  Aryabhata Dec 23 '10 at 20:56
@Moron why $n-1$? If $n \geq 1$ then $n-1$ would be $0$ which is less then one. Also, how do I know that the right side of the hint is proving anything about the right side of the problem? I realize that it does, but how do you prove that. –  qw3n Dec 23 '10 at 21:04
For the base cases you need to consider $n=1$, $n=2$, and the induction step will assume $n > 2$. Usually when you use strong induction, the base case needs more than just $n=1$. Try applying the expansions for $a^n -1$ and $a^{n-1} - 1$ (which you assume is true as part of the strong induction hypothesis) on the right side of the hint and see what you get... –  Aryabhata Dec 23 '10 at 21:05

HINT $\$ Put $\rm\ f(n) = a^n+a^{n-1}+\:\cdots\:+1\:.\ \$ Then

$\rm\ a^{n+1}-1\ = \ (a+1)\ (a^n-1) - a\ (a^{n-1}-1)$

$\rm\phantom{\ a^{n+1}-1\ } =\ (a+1)\ ((a-1)\ f(n-1) - a\ (a-1)\ f(n-2))\quad$ by strong induction

$\rm\phantom{\ a^{n+1}-1\ } =\ (a-1)\ ((a+1)\ f(n-1)- a\ f(n-2))\quad$

$\rm\phantom{\ a^{n+1}-1\ } =\ (a-1)\ (\:f(n-1) + a\ (f(n-1)-f(n-2))$

$\rm\phantom{\ a^{n+1}-1\ } =\ \ldots$

$\rm\phantom{\ a^{n+1}-1\ } =\ (a-1)\ f(n)$

-

Sometimes the easiest way to figure out an induction argument like this is to prove a particular case. I'll take care of proving $n = 3$, assuming you've already proven $n = 1$ and $n = 2$.

By the hint, we have $$a^{3} - 1 = (a + 1)(a^2 - 1) - a(a - 1)$$

But the cases $n = 1$ and $n = 2$ hold, so we rewrite this as $$a^{3} - 1 = (a + 1)(a - 1)(a + 1) - a(a - 1)$$

Now by factoring $(a - 1)$ on the right hand side, we have $$a^3 - 1 = (a - 1)(a^2 + 2a + 1 - a) = (a - 1)(a^2 + a + 1)$$

This is less interesting than the case $n = 4$; try to work that out on your own! After that, you should be able to work out a general $n + 1$ case.

-

HINT $\ \$ Show that $\rm\ (a^{n+1}-1)/(a-1)\$ and $\rm\ a^n+a^{n-1}+\:\cdots\:+1\$ are both solutions of the recurrence $\rm\ f(n+2)\ = (a+1)\ f(n+1) - a\ f(n)\$ with identical initial conditions $\rm\ f(1),\ f(0)\:.\ \ \$
Now use strong induction to prove the uniqueness theorem for solutions of such difference equations (which is very easy). This is the essence of the calculation in my other answer.

As I've emphasized in many posts here uniqueness theorems provide powerful tools for proving equalities. Luckily, here, the uniqueness theorem for difference (vs. differential) equations has an absolutely trivial proof by way of (strong) induction.

Note that the corresponding first-order case is essentially telescopy, also known as the fundamental theorem of difference calculus.

-