Proof related to Fibonacci sequence Could anyone help me with this problem?
$$
\sum_{j=0}^{n}\binom{n}{j}F_{n+1-j}= F_{2n+1}
$$
I used induction and was able to get to this:
$$
2\sum_{j=0}^{n}\binom{n}{j}F_{n-j}= F_{2n}
$$
However I still do not know how to prove the second equality. Really appreciate any help
 A: It’s not true that
$$F_{2n}=2\sum_{j=0}^n\binom{n}jF_{n-j}\;:$$
you have an extra factor of $2$ there. It should be
$$F_{2n}=\sum_{j=0}^n\binom{n}jF_{n-j}\;.$$
For example, with $n=3$ we have
$$\begin{align*}
\sum_{j=0}^3\binom3jF_{3-j}&=\binom30F_3+\binom31F_2+\binom32F_1+\binom33F_0\\
&=1\cdot2+3\cdot1+3\cdot1+1\cdot0\\
&=8\;,
\end{align*}$$
and $8$ is indeed $F_6$. 
You can use the corrected result to get the other identity. Note first that $\binom{n}j=\binom{n}{n-j}$ so we have
$$F_{2n}=\sum_{j=0}^n\binom{n}jF_{n-j}=\sum_{j=0}^n\binom{n}{n-j}F_{n-j}=\sum_{k=0}^n\binom{n}kF_k\;,$$
where the last step is simply substituting $k=n-j$. Then
$$\begin{align*}
F_{2n+1}&=F_{2n+2}-F_{2n}\\
&=\sum_{k=0}^{n+1}\binom{n+1}kF_k-\sum_{k=0}^n\binom{n}kF_k\\
&=\sum_{k=0}^{n+1}\left(\binom{n+1}k-\binom{n}k\right)F_k\\
&=\sum_{k=0}^{n+1}\binom{n}{k-1}F_k\\
&=\sum_{k=0}^n\binom{n}kF_{k+1}\\
&=\sum_{k=0}^n\binom{n}{n-k}F_{k+1}\\
&=\sum_{j=0}^n\binom{n}jF_{n+1-j}\;,
\end{align*}$$
as desired.
A: (For future reference as an exercise in integration.) Suppose we seek
to verify that
$$F_{2n} = \sum_{j=0}^n {n\choose j} F_{n-j}$$
with $F_q$ being a Fibonacci number. These have generating function
$$f(z) = \frac{z}{1-z-z^2}$$
and hence
$$F_{n-j} = 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n-j+1}} \frac{z}{1-z-z^2} \; dz.$$
We get for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{z}{1-z-z^2} 
\sum_{j=0}^n {n\choose j} z^j
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{z}{1-z-z^2} 
(1+z)^n
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} \frac{1}{1-z-z^2} 
(1+z)^n
\; dz.$$
Now put $z/(1+z) = v$ so that $z = v/(1-v)$ and $dz = 1/(1-v)^2 dv$ to
get
$$\frac{1}{2\pi i}
\int_{|v|=\gamma} \frac{1}{v^{n}} 
\frac{1}{1-v/(1-v)-v^2/(1-v)^2}
\frac{1}{(1-v)^2}
\; dv
\\ = \frac{1}{2\pi i}
\int_{|v|=\gamma} \frac{1}{v^{n}} 
\frac{1}{(1-v)^2-v(1-v)-v^2}
\; dv
\\ = \frac{1}{2\pi i}
\int_{|v|=\gamma} \frac{1}{v^{n}} 
\frac{1}{1-2v+v^2-v+v^2-v^2}
\; dv
\\ = \frac{1}{2\pi i}
\int_{|v|=\gamma} \frac{1}{v^{n}} 
\frac{1}{1-3v+v^2}
\; dv.$$
This is
$$[v^n] \frac{v}{1-3v+v^2}.$$
Observe  however  that  the  generating  function of  the  even  index
Fibonacci numbers is given by
$$\left.\left(\frac{1}{2} f(z) + \frac{1}{2} f(-z)
\right)\right|_{z^2=w}.$$
We thus have for the generating function
$$\left. \left(\frac{1}{2} \frac{z}{1-z-z^2} 
- \frac{1}{2} \frac{z}{1+z-z^2}\right)\right|_{z^2=w}
\\ = \left. \frac{1/2z(1+z-z^2)-1/2z(1-z-z^2)}{(1-z^2-z)(1-z^2+z)}
\right|_{z^2=w}
\\ = \left. \frac{z^2}{(1-z^2)^2-z^2}
\right|_{z^2=w}
= \frac{w}{1-3w+w^2}$$
and the claim is established.
