4
$\begingroup$

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.

  • 0
    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...2010-12-23

3 Answers 3

3

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)$

2

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.

1

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.