Show that $\sum_{j=0}^{n}{n+j\choose 2j}5^j...$ I am trying to show that, $$\sum_{j=0}^{n}{n+j\choose 2j}5^j=\frac{\phi^{-4n}}{1+\phi^4}+\frac{\phi^{4n}}{1+\phi^{-4}}$$
where $\phi=\frac{1+\sqrt{5}}{2}$ and $n\ge 0$
An atempt:
$$\sum_{j=0}^{n}{n+j\choose n-j}5^j$$
$$\sum_{j=0}^{n}\frac{(n+j)!}{(n-j)!(2j)!}\cdot5^j$$
$$\sum_{j=0}^{n}\frac{(n-1)(n-2)(n-3)\cdots(n-j+1)\times n(n+1)(n+2)(n+3)\cdots(n+j)}{(2j)!}\cdot5^j$$
$$\sum_{j=0}^{n}\frac{(n^2-1)(n^2-4)(n-9)\cdots(n^2-(j-1)^2)\times n(n+j)}{(2j)!}\cdot5^j$$
I can't simplify this sum, it seems like the method I am trying to do it is incorrect.
Help reqiured, thank you.
 A: Let's call $b_n$ the expresion on the LHS and $a_n$ the expression on the RHS. We want to show that $b_n=a_n$.
In one hand, since $\phi^{-4}$ and $\phi^4$ are roots of $x^2-7x+1$ we have that $a_{n+1}=7a_{n}-a_{n-1}$.
Let's prove that the $b_n$'s satisfy the same recursive relation.
Indeed $$7b_n-b_{n-1}=5b_n+2b_n-b_{n-1}=\sum_{j=0}^n {n+j\choose 2j}5^{j+1}+\sum_{j=0}^n 2{n+j\choose 2j}5^{j}-\sum_{j=0}^{n-1} {n-1+j\choose 2j}5^{j}=\sum_{j=1}^{n+1} {n+j-1\choose 2j-2}5^{j}+\sum_{j=0}^n 2{n+j\choose 2j}5^{j}-\sum_{j=0}^{n-1}{n-1+j\choose 2j}5^{j}$$
You can prove that $${n+j-1\choose 2j-2}+2{n+j\choose 2j}-{n-1+j\choose 2j}={n+1+j\choose 2j}$$
Which implies that the sum above equals $b_{n+1}$.
Hence $b_{n+1}=7b_{n}-b_{n-1}$. Now, just need to check $a_0=b_0$ and $a_1=b_1$.
A: We use the coefficient of operator $[z^j]$ to denote the coefficient of $z^j$ in a series. This way we can write for instance
\begin{align*}
[z^j](1+z)^n=\binom{n}{j}
\end{align*}

We obtain
\begin{align*}
\color{blue}{\sum_{j=0}^n}\color{blue}{\binom{n+j}{n-j}\,5^j}
&=\sum_{j=0}^n[z^{n-j}](1+z)^{n+j}5^{j}\\
&=[z^n](1+z)^n\sum_{j=0}^{\infty}\left(5z(1+z)\right)^j\tag{1.1}\\
&\,\,\color{blue}{=[z^n]\frac{(1+z)^n}{1-5z-5z^2}}\tag{1.2}
\end{align*}

We set in (1.1) the upper limit of the series to $\infty$ without changing anything, since powers of $z$ greater $n$ are ignored due to the coefficient of operator $[z^n]$. This way we can use the geometric series expansion in (1.2).
We now use a clever change of variables stated as rule 5 in section 1.2 of Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. Rule 5 adapted for this special case is:
\begin{align*}
[z^n]A(z)f^{n}(z)
&=[y^n]\left.\frac{A(z)f(z)}{f(z)-zf^{\prime}(z)}\right|_{z=g(y)}\tag{2}
\end{align*}
Here we have $f(z)=(1+z)$ and $g=g(y)$ is the inverse function of
\begin{align*}
\frac{z}{f(z)}=\frac{z}{(1+z)}=y\tag{3}
\end{align*}
We obtain
\begin{align*}
&z=\frac{y}{1-y}\\
\end{align*}

We get from (1.2),(2) and (3)
\begin{align*}
\color{blue}{[z^n]\frac{(1+z)^n}{1-5z-5z^2}}&=[y^n]\left.\frac{1+z}{(1+z)-z}\,\frac{1}{1-5z-5z^2}\right|_{z=\frac{y}{1-y}}\\
&=[y^n]\left.\frac{1+z}{1-5z-5z^2}\right|_{z=\frac{y}{1-y}}\\
&=[y^n]\frac{1-y}{1-7y-y^2}\tag{4}\\
&=[y^n]\frac{1-y}{\left(y-\phi^4\right)\left(y-\phi^{-4}\right)}\tag{5}\\
&=[y^n]\left(\frac{1}{1+\phi^4}\,\frac{1}{1-\phi^{-4}y}+\frac{1}{1+\phi^{-4}}\,\frac{1}{1-\phi^{4}y}\right)\tag{6}\\
&\,\,\color{blue}{=\frac{\phi^{-4n}}{1+\phi^4}+\frac{\phi^{4n}}{1+\phi^{-4}}}
\end{align*}
and the claim follows.

Comment:

*

*In (4),(5) we find $y=\frac{1}{2}\left(7\pm3\sqrt{5}\right)$ are the roots of $1-7y-y^2=0$. We obtain
\begin{align*}
\phi^4&=\left(\frac{1}{2}\left(1+\sqrt{5}\right)\right)^4=\frac{1}{2}\left(7+3\sqrt{5}\right)\\
\phi^{-4}&=\frac{2}{7+3\sqrt{5}}=\frac{1}{2}\left(7-3\sqrt{5}\right)
\end{align*}


*In (6) we make a partial fraction decomposition.


*In (7) we select the coefficient of $y^n$.
