0
$\begingroup$

Let Fn be the Fibonacci number, with $F_0 = 1, F_1 = 1$. Prove the identity $2F_n = F_{n+1} + F_{n−2}$ by using generating functions.

I know the generating function for the shifted Fibonacci Sequence, $F_n$ with $F_0=1$ and $F_1=1$ but not sure how to incorporate the $2$.

$\endgroup$
0
$\begingroup$

You may prove it by using the direct formula for Fibonacci numbers $$F_k=\frac{a^k-b^k}{\sqrt{5}}, a+b=1, ab=-1,a^2=a+1, b^2=b+1$$, Then $$F_{n+1}+F_{n-2}= \frac{a^{n+1}-b^{n+1}}{\sqrt{5}}+\frac{a^{n-2}-b^{n-2}}{\sqrt{5}}$$ $$=\frac{1}{\sqrt{5}}\left(a^n(a+\frac{1}{a^2})-b^n(b+\frac{1}{b^2}) \right)$$ note that $a+1/a^2=a+b^2=a+b+1=2$, then $$F_{n+1}+F_{n-2}= \frac{2}{\sqrt{5}}[a^n-b^n]=2 F_n$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If you're going to avoid generating functions, you may as well prove this from $F_{n+1}=F_n+F_{n-1}$ and $F_n=F_{n-1}+F_{n-2}$ and middle school algebra. $\endgroup$ – Matthew Daly Jan 25 at 18:10
  • $\begingroup$ Yes, you are right, but I like it this way. $\endgroup$ – Z Ahmed Jan 25 at 18:14

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.