Hi,
today I'm really stuck with strong inductions...
Let be the Fibonacci number. Prove that for all m ≥ 1 and all n, .
Can someone help me with it?
Looked it up in my book. Here's how it describes it (reworded of course):
First it describes it as a lemma, which needs to be proven (using the statements for n = k - 1 and for n = k to prove the statement for n = k + 1 so you'll be needing two base cases instead of just one meaning we have to check for n = 1 and n = 2).
When n = 1, we have to verify that . Now since , we must verify that which must be true since it's a defining relationship for the Fibonacci numbers.
When n = 2, then we need to verify that . Now since and , then we need to verify that which is true based on the following:
Next we assume the statement holds for n = k - 1 and n = k or
and which is the
induction hypothesis. From out of the next series of equations:
=
=
=
=
=
we have which is the statement for n = k + 1 which completes the proof.