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.

  • $\begingroup$ Your inductive step fails for $n = 1$ if you don't know anything about $l_0$. $\endgroup$ – Qiaochu Yuan Sep 28 '12 at 2:49

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.