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

2

In the induction step for $\,n = 1\,$ you implicitly use $\,l_0 = f_{-1}\! + f_{1}\, (= 1 + 1).\ $ The induction proof essentially shows that if $\,l_n = f_{n-1} + f_{n+1}$ holds true for two successive values $\, n = k,\, k\!+\!1,\:$ then it remains true for all $\,n \ge k.$

Equivalently $\ g_n = f_{n-1}\!+f_{n+1}\!-l_n\ $ satisfies the Fibonacci recurrence (being a sum of solutions) but has initial conditions $\:g_0\! = 0,\,\ g_1\! = 0,\:$ so $\:g_n\! = 0\:$ by the uniqueness theorem for recurrences. Said uniqueness theorem has a straightforward two-line inductive proof.

As I often emphasize, uniqueness theorems provide powerful tools for proving equalities.