I have found a startling proof by induction which is clearly wrong.
Let L(n) represent Lucas numbers. L(0)=2, L(1)=1 L(n) = L(n-1) + L(n-2)
Let F(n) denote a Fibonacci number. F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
We set out to prove the premise that L(n) = F(n+3), for all n greater than 0
Base Step : An easy substitution of n = 0 verifies this.
Hypothesis step : For all j in between 0 and K, we assume that L(k) = F(k+3)
Induction step : We need to prove that L(k+1) = F(k+4)
Since we have used the principles of strong induction, we know that P(k-1) is also true.
Therefore, L(k-1) = F(k+2) We add this step and out induction hypothesis.
LHS : L(k-1) + L(k) = L(k+1) RHS : F(K + 2) + F(k +3) = F(K + 4)
Our induction step is proved. QED?
This result is clearly false. Can someone explain why? I have been told that strong and weak induction are equivalent.
In your inductive step, you use both $P(k)$ and $P(k-1)$. However, in your base step, you only check for one value.
In other words, your inductive step is true for $n \geq 2$, so you need to include $n=1$ in your base step.