1

The problem i'm trying to solve is:

Use the second principle of finite induction to establish that: $$a^n -1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3}+\cdots+a+1)$$ for all $n \ge 1$

I have found a solution online that reads: $$ \mbox{For }k=1: \ a^1-1 =a-1=(a-1)(a^0)=a-1 $$

\begin{align} k \Rightarrow k+1: \ a^{k+1} -1 &= a^{k+1}-a^k-a+a^k+a-1\\ &=a(a^k-1)+a^k-1-a(a^{k-1} -1)\\ &=(a+1)(a^k-1)-a(a^{k-1}-1) \end{align} Use second principle of induction for $k,\ k-1$: \begin{align} &=(a+1)[(a-1)(a^{k-1}+a^{k-2}+\cdots+a+1)] \\ &\qquad \; \; -a[(a-1)(a^{k-2}+a^{k-3}+\cdots+a+1)]\\ &=(a-1)[(a)(a^{k-1}+a^{k-2}+\cdots+a+1)\\ &\qquad \quad \ \, +(1)(a^{k-1}+a^{k-2}+\cdots+a+1)\\ &\qquad \quad \ \,-(a)(a^{k-2}+a^{k-3}+\cdots+a+1)]\\ &=(a-1)[(a^k+a^{k-1}+a^{k-2}+\cdots+a^2+a)+1] \end{align} $\therefore$ works for $k+1$

My problem:

I understand all the steps used for the principle of second induction however i do not understand how you are supposed to deduce that you need: $$a^{k+1} -1 = (a+1)(a^k-1)-a(a^{k-1}-1)$$ To clarify i understand the logic that leads to the equation above, but do not understand how you know to try to make it. Is there something specific about the format $ (a+1)(a^k-1)-a(a^{k-1}-1)$ that allows you to know it is needed, or has the format just been found through any possible means that leads to $(a^k-1)$ and $(a^{k-1}-1)$ being used?

Sonny Da Silva-Peters
  • 316
  • 1
    Why are you using induction to prove this statement? You can just distribute. – Franklin Pezzuti Dyer Jun 14 '17 at 20:14
  • I'm mostly curious as to how the answer that i found relating to the question in the book that stated you had to use induction works, not so much in an answer to the proof. (to answer your question the book said to do it that way) – Sonny Da Silva-Peters Jun 14 '17 at 20:16
  • Okay, I see now. – Franklin Pezzuti Dyer Jun 14 '17 at 20:17
  • 1
    @SonnyDaSilva-Peters I'm not completely sure what your doubt is, but my opinion is: when going to $;k+1;$, one begins doing some algebraic hokus pokus trying hard to get some expressions where to use the inductive hypothesis, which is the leading light almost anyone doing induction follows: how, where, when do I "put in" the inductive hypothesis to use that and get what I want. – DonAntonio Jun 14 '17 at 20:18
  • okay, yeah i think that answers my suspicion that the "algebraic hokus pokus" doesn't have a usual pattern but is compiled of logical steps that seem to lead to a expression where you could use the induction hypothesis. (what does @DonAntonio for instance do, don't users get notifications anyway?) – Sonny Da Silva-Peters Jun 14 '17 at 20:25
  • The "@" symbol "pins" people, and a little red dot appears in the upper left part of the page telling you someone has directed you a question, comment, etc. – DonAntonio Jun 14 '17 at 20:28
  • @DonAntonio oh okay, thank you for your help – Sonny Da Silva-Peters Jun 14 '17 at 20:30
  • 1
    I think knowing to do it a certain way is partly just trying to introduce the expressions for $a^k - 1$ and $a^{k-1} - 1$ to be able to use the induction hypothesis, and partly algebraic skill in being able to foresee the result. That being said, I can't follow the calculation above because at one point you seem to use $a^{k-1} - 1 = (a-1)(a^{k-1} + \dots + 1)$, when it should really be $a^{k-2} + \dots + 1$. Also, I think this method, if it works, is unnecessarily complicated. I'm going to add a different approach below. – user49640 Jun 14 '17 at 21:35
  • No, there's still a place where $a^{k-1} - 1$ is replaced by the wrong thing. – user49640 Jun 14 '17 at 22:05
  • okay, i believe now it should be all edited, hopefully... – Sonny Da Silva-Peters Jun 14 '17 at 22:08
  • All right, it works now. – user49640 Jun 14 '17 at 22:26
  • Presumably there is now a first, second, and infinite principle of induction. – DanielV Jun 15 '17 at 04:35

4 Answers4

1

When going to $k+1$, one begins doing some algebraic "hokus pokus" trying hard to get some expressions where to use the inductive hypothesis, which is the leading light almost anyone doing induction follows: how, where, when do I "put in" the inductive hypothesis to use that and get what I want.

$\mbox{-}$ DonAntonio (from comments just placed as answer)

Sonny Da Silva-Peters
  • 316
1

I'm just going to do the induction step here, for $k \to k + 1$, to show that it can be done in a simpler and more transparent way.

So assume you already know that $$a^k - 1 = a^{k-1} + a^{k-2} + \dots + a + 1.$$ Then, using the induction hypothesis on the second line, we have \begin{align} (a-1)(a^k + a^{k-1} + \dots + a + 1) &= (a-1)a^k + (a-1)(a^{k-1} + a^{k-2} + \dots + a + 1) \\ &= a^{k+1} - a^k + a^k - 1 \\ &= a^{k+1} - 1. \end{align} This proves the result for $k + 1$.

Edit Just in case you haven't seen it, here is the proof without induction. (Technically, there's probably some kind of induction hidden somewhere inside it, but it's not formalized.) $$ \begin{align} (a-1)(a^{n-1} + a^{n-2} + \dots + a + 1) &= a(a^{n-1} + a^{n-2} + \dots + a + 1) - (a^{n-1} + a^{n-2} + \dots + a + 1)\\ &= a^n + a^{n-1} + \dots + a^2 + a - (a^{n-1} + a^{n-2} + \dots + a + 1) \\ &= a^n - 1. \end{align} $$

user49640
  • 2,704
  • yes this is a much better proof, thanks. My question was trying to understand the steps in the other answer but seeing another way of solving it ,far more efficiently, is also helpful – Sonny Da Silva-Peters Jun 14 '17 at 21:55
  • As I said in my comments, there's at least one mistake in what you wrote above. It may be able to be corrected, but regardless, I think whoever wrote that proof sort of got lost. – user49640 Jun 14 '17 at 21:58
  • i think i edited it so it should be okay now: $$-(a)(a^{k-2}+a^{k-3}+\cdots+a+1)$$ thereby allwoing it to turn into $$-(a^{k-1}+a^{k-2}+\cdots+a^2+a)$$ and then cancelling out with $$+(a^{k-1}+a^{k-2}+\cdots+a+1)$$ to form $$+1$$ – Sonny Da Silva-Peters Jun 14 '17 at 22:02
1

Observe that $$a^{n+1}-1=(a^n-1)+(a^{n+1}-a^n)=(a^n-1)+(a-1)a^n.$$ So if $a^n-1=(a-1)(1+...+a^{n-1})$ then $$a^{n+1}-1=(a^n-1)+(a-1)a^n=$$ $$=(a-1)(1+...+a^{n-1})+(a-1)a^n=$$ $$=(a-1)([1+...+a^{n-1}]+a^n)=$$ $$=(a-1)(1+...+a^n).$$ This is a frequently used method. For example to prove that $1+...+n=F(n)=n(n+1)/2$ for all $n\in \mathbb N,$ after noting that it is valid when $n=1,$ we have $1+...+(n+1)=(1+...+n)+(n+1).$

So if $(1+...+n)=F(n)$ then $1+...+(n+1)=(1+...+n)+(n+1)=F(n)+(n+1)=F(n+1). $

DanielWainfleet
  • 57,985
1

If you have any inclination towards mathematics at all, you know that the equation

$a^n - 1 = 0$

can be solved by letting $a = 1$. It was not that long ago that you 'could just see' that

$x^2 - 1 = (x - 1) (x + 1)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ (1)

When you divide $x^3 - 1$ by $x -1$, you realize you are on the road to discovery when get

$x^3 - 1 = (x -1) (x^2 + x^1 + x^0)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,$ (2)

Emboldened by all this, you want to prove that

$x^6 - 1 = (x -1) (x^5 + x^4 + x^3 + x^2 + x^1 + x^0)\;\;\;\;\;$ (3)

by making use of (1) and (2):

$x^6 - 1 = (x^3 + 1) (x^3 - 1) = (x^3 + 1) (x - 1) (x^2 + x^1 + x^0) =$
$\;\;\;(x - 1) \,(x^3 + 1)\, (x^2 + x^1 + x^0)=$
$\;\;\;(x - 1)\,[ \,x^3\, (x^2 + x^1 + x^0)\,+ (x^2 + x^1 + x^0)\,]$

You don't even bother finishing the work - you 'can see it'.

Before getting formal and using strong induction (also called the second principle of finite induction), you have a nagging feeling (odd exponents), so you write down

$x^7 - 1 = x (x^3 + 1) (x^3 - 1) + (x -1)$

Amazingly, you don't have to go on. Working on the right side, you factor out $x - 1$ and can 'see' that the coefficients are all '+1' and that each $x^k \;\;\; \text {for } 0 \le k \le 6$ appears.

Suddenly you hear laughter! A friend explains to you that they can see the same thing for the general case without doing any work! They tell you to take a look at the article Telescoping Sum. As they walk away you hear them say something about a geometric series.

Now you realize that you can figure all this out by using the powerful capital-sigma notation:

${\displaystyle \sum _{i{\mathop {=}}m}^{n}a_{i}=a_{m}+a_{m+1}+a_{m+2}+\cdots +a_{n-1}+a_{n}}$

If you just accept that you can do so many general manipulations under this notation, you can simnply dispense with induction if you still feel it is necessary to prove this.

CopyPasteIt
  • 11,366