What's the difference between weak induction and strong induction?

Question

This seems to be the structure of both strong and weak induction:
1. Prove a base case using an example.
2. Set up your inductive hypothesis by setting n = k and assuming it is true.
3. Set n = k +1 and prove it is true using previous steps.

What's the difference between these two inductions?

Answer 1

With weak induction you assume that the statement is true for n = k and show that this implies it is true for n = k + 1.



With strong induction you assume that the statement is true for all integers n ≤ k and show that this implies it is true for n = k + 1.



In most proofs, weak induction is sufficient.

Answer 2

Weak Induction

Answer 3

Strong Induction

Answer 4

This Site Might Help You.



RE:

What's the difference between weak induction and strong induction?

This seems to be the structure of both strong and weak induction:

1. Prove a base case using an example.

2. Set up your inductive hypothesis by setting n = k and assuming it is true.

3. Set n = k +1 and prove it is true using previous steps.



What's the difference between these two...