Strong Induction: Examples and Explanation

[gsingh2011]

I understand weak induction but I'm confused on strong induction. Can someone give me a simple example where you would use strong induction and not weak?

 

[Martin Rattigan]

Proving that any natural number > 1 can be expressed as the product of (one or more) primes.

 

[disregardthat]

Strong induction is characterized by that instead of proving P(k) --> P(k+1), where P(n) is a proposition for a number n, we rather prove that ( P(1) and P(2) and ... and P(k) )--> P(k+1). It is stronger in the sense that we use more information for the inductive step.

For example; if you want to prove a specific formula for a difference equation, say x_{n-2}+x_{x-1}=x_n, by induction, you will need, for the inductive step, that both x_{k-1} and x_{k} satisfy the formula in order to prove the formula for x_{k+1}. In other words; you will need P(k-1) and P(k) to prove P(k+1), where P(n) is the proposition that x_n satisfies the formula.

 

[gsingh2011]

Strong induction is characterized by that instead of proving P(k) --> P(k+1), where P(n) is a proposition for a number n, we rather prove that ( P(1) and P(2) and ... and P(k) )--> P(k+1). It is stronger in the sense that we use more information for the inductive step.

For example; if you want to prove a specific formula for a difference equation, say x_{n-2}+x_{x-1}=x_n, by induction, you will need, for the inductive step, that both x_{k-1} and x_{k} satisfy the formula in order to prove the formula for x_{k+1}. In other words; you will need P(k-1) and P(k) to prove P(k+1), where P(n) is the proposition that x_n satisfies the formula.

So is this pretty much like saying you have more than one base case? Specifically, you have as many base cases as there are variables?

 

[disregardthat]

So is this pretty much like saying you have more than one base case? Specifically, you have as many base cases as there are variables?

The base case P(1) must of course be proven. But no, you don't need more than one base case. You'd think so, but you can see it is 'taken care of' by the inductive step. The general proof of the inductive step must be valid for n = 2, so another base case need not be established, but care must be taken. I.e. in the inductive step, you assume ( P(1) and P(2) and ... and P(k) ), but you must consider the possibility k = 1; in which case you do not have P(k) and P(k-1), but only P(k). This can however easily be verified by a direct proof.

Other examples would perhaps require ( P(1) and P(2) and ... P(k) ) to prove P(k+1), and not just ( P(k-1) and P(k) ) as in this example.

Strong induction can be proven logically equivalent to weak induction, so it's not stronger in that sense.