3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ These two concepts are formally different, but they are essentially the same thing. $\endgroup$
    – Crostul
    Nov 8, 2016 at 11:50
  • $\begingroup$ Simple induction is just a special case of so-called strong induction, so every proof by simple induction is a proof by strong induction. Thus, no such example is possible. The only difference is in the form of the induction hypothesis. In strong induction you assume that the result is true for all $k<n$ that are at least as large as your starting point, while for ordinary induction you assume it only for $n-1$. $\endgroup$ Nov 8, 2016 at 11:50
  • $\begingroup$ There must be a difference. My teacher fails me when i use Simple Induction and I should have used Strong Induction. I know the definition for both terms but when i look at them i cant stop but thinking that that is the same thing. But my teacher says no it is not the same thing and i can't understand her argument for why it is not. So therefore i made this post hoping someone could elighten me. $\endgroup$
    – Nulle
    Nov 8, 2016 at 11:57
  • $\begingroup$ You know it is everything about this. I cant tell the difference between the procedures and i cant tell when to use what. $\endgroup$
    – Nulle
    Nov 8, 2016 at 11:58
  • 1
    $\begingroup$ @Nulle Essentially you should never try to use simple induction. Think of the principle of strong induction as a "licence to use the fact that $P$ is true for smaller values than $n$, when trying to prove $P(n)$". If it turns out that during your proof, you would find it helpful to use $P$ for a smaller value, then feel free to use it. If it turns out that the natural such smaller value is $n-1$, then so be it; you've just recovered simple induction. (Thanks to Prof Imre Leader for this viewpoint and for many other things.) $\endgroup$ Nov 8, 2016 at 20:53

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In your answer Let $N\ge 2$ given is pointed out, but why in this answer the formula of strong induction only says $m\le n$, not $0\le m\le n$? link: mathoverflow.net/a/37971/104425 . (I commented there, please help.) $\endgroup$ Jul 23, 2019 at 9:22
  • 1
    $\begingroup$ @PostalModel: There are no $m<0$ in the linked answer, since the "base set" ${\mathbb N}$ is assumed to begin at $0$. $\endgroup$ Jul 23, 2019 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.