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