3
$\begingroup$

Define the Lucas numbers to be

$$l_n = l_{n-1} + l_{n-2} $$

if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$.

I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by $f_n$ I mean the n'th Fibonacci number) but never used the initial condition $l_0 = 2$, so I would like for someone to point out the flaw.

Proof: Instead of using regular induction, let's use strong induction. The base case is obvious $l_1$ is obvious. Now suppose the equation holds for $1 \le n$ for some $n$. Using the inductive hypothesis and the definition of fibonacci numbers

$$l_{n+1} = l_{n} + l_{n-1} = f_{n-1} + f_{n+1} + f_{n-2} + f_{n} = f_n + f_{n+2}$$

I can't find out the flaw in my reasoning.

  • 0
    Your inductive step fails for $n = 1$ if you don't know anything about $l_0$.2012-09-28

1 Answers 1