<s>[INST] 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.
 [/INST] 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$.
</s>