[Math] Simple Induction vs Strong Induction proof.

induction

I am having a great deal of trouble grasping the essential difference between Simple induction and Strong Induction proof.

I was hoping someone here would do me the honor of making an example. First illustrating simple induction then the same example using strong induction and then point out the essential difference between these two procedures.

My teacher showed us how you could solve F_n <= 2^n. Fn being fibbonacci. 

F0 = 0, F1 = 1, Fn =Fn-1 + Fn-2

By simple induction she said it would be solved like this:

if P(1) = true
Then assume P(n) is true for all n in positive integers
Show that P(n+1) is true.
P(n+1) is true if Fn+1<=2^{n+1}
Fn+1 = Fn+Fn-1 
     <= Fn + Fn 
     <= 2Fn 
     <= 2*2^n
     <= 2^n+1
Then proof by simpel induction is complete. 

The same expression can be proofed by Strong Induction like this:'
if P(1) is true 
Then assume that P(i) is true for all i<=k
Show that P(k+1) is true. 
P(k+1) is true if Fk+1 <= 2^k+1
Fk+1 = fk + fk-1
     <= 2^k + 2^k-1
     <= 2^k + 2^k * 2^-1
     <= 2^k(1+0,5)
     <= 2^k(3/2)
     <= 2^k * 2
     <= 2^k+1
The proof by Strong induction is complete

I cant graps at all what my teacher is doing in the strong induction proof. Can someone tell me and point out the essential difference between the two procedures?

Thank you in advance.

Best Answer

Here is an example:

Theorem. Any natural number $n>1$ can be factored into $\geq1$ primes.

In the proof we may use the principle $$ x\geq y>1\qquad\Rightarrow\qquad x\,y>x\geq y\ .\tag{*}$$

Here simple induction is of no help, because there is no obvious connection between the factorizations of $n$ and $n+1$, e.g., $48$ and $49$. But strong induction does the job: The number $2$ is prime. Let an $N\geq2$ be given, and assume the strong induction hypothesis (SIH): The statement is true for all $n\in[2\>..\,N]$. Then the number $N+1$ is either prime, or a product $N+1=n'\cdot n''$ whereby $$2\leq \ n'\leq n'' \ \leq N$$ (here the principle $(*)$ was used). The strong induction hypothesis (SIH) then allows to conclude that $N+1$ can be written as a product of $\geq1$ primes.

(Answering your comment: The second proof of $F_n\leq2^n$, apart from missing a dozen parentheses, uses "strong induction" in so far as for the proof of $F_{n+1}\leq 2^{n+1}$ it not only uses $F_n\leq 2^n$, but also explicitly $F_{n-1}\leq 2^{n-1}$. But it does not use that $F_k\leq 2^k$ is true for all $k\leq n$.)

Related Question