## Strong Induction

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?

 Proving that any natural number > 1 can be expressed as the product of (one or more) primes.
 Recognitions: Science Advisor 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.

## Strong Induction

 Quote by Jarle 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?

Recognitions: