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
    Hmm, your correction came in 6 seconds after mine!2010-12-23
  • 0
    @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.2010-12-23
  • 0
    To prove for $n+1$, using the hint, you need to assume for $n-1$ and $n$, so it is using strong induction.2010-12-23
  • 0
    @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.2010-12-23
  • 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