Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Your inductive step fails for $n = 1$ if you don't know anything about $l_0$. –  Qiaochu Yuan Sep 28 '12 at 2:49

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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