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

(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.
