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$
2
  • $\begingroup$ math.meta.stackexchange.com/questions/5020/… $\endgroup$
    – user645636
    Jan 25, 2020 at 15:57
  • 1
    $\begingroup$ Can you tell us the generating function then? That said, this question is far easier to solve from the basic definition. $\endgroup$
    – user694818
    Jan 25, 2020 at 18:06

1 Answer 1

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$$

$\endgroup$
2
  • 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$
    – user694818
    Jan 25, 2020 at 18:10
  • $\begingroup$ Yes, you are right, but I like it this way. $\endgroup$
    – Z Ahmed
    Jan 25, 2020 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.