also never quite understood difference between strong vs weak induction, any examples to help make sense of this?
Say you have a statement you're trying to prove by induction.
A normal induction proof would go like "if this statement is true for
k then it must also be true for
k + 1."
A strong induction proof would be more like "if this statement is true for
all numbers less than or equal to k then it must also be true for
k + 1."
This extra condition gives you more to work with, and you sometimes need it for harder proofs.
(You may not need to make the assumption for
every single number less than
k, but you would need to make the assumption for at least a few.)
I vaguely remember doing a question related to the Fibonacci numbers with strong induction - you can try to find it online.