Suppose that $$ A=\begin{bmatrix}a_{11}&a_{21}\\a_{21}&a_{22}\end{bmatrix}, \ \ B=\begin{bmatrix}d&-1\\1&0\end{bmatrix}. $$ and $$A=B^N$$ Show that $$a_{11}=\sum_{i=0}^{[N/2]}(-1)^i {C_{N-i}^i} d^{N-2i}$$
where ${C_{N-i}^i}=\frac{(N-i)!}{i!(N-2i)!}$.
Warning: This is not the shortest proof. The simplest way to prove the desired identity is via induction. Instead, I'll give a demonstration of two different techniques: I'll determine $B^N$ by first diagonalizing $B$, and then show via a formal power series that the expression so obtained also my be found from desired expansion given above.
Finding $A=B^N$
Note that the characteristic polynomial of $B$ is $\det(B-\lambda I)=\lambda^2-d\lambda-1=0$, which implies $$ \lambda =\frac{1}{2}\left[d\pm \sqrt{d^2+4}\right]=\cosh(\tau)\pm \sinh(\tau)=e^{\pm \tau}$$ where $d=2\cosh \tau $. Then $$ B - e^{\pm \tau} I = \left(\begin{matrix} 2\cosh\tau -e^{\pm \tau} & -1 \\ 1 & -e^{\pm \tau}\end{matrix}\right)=\left(\begin{matrix} e^{\mp \tau} & -1 \\ 1 & -e^{\pm \tau}\end{matrix}\right)$$ which has eigenvectors $v_{\pm}=(e^{\pm \tau},1)^T$. Hence we may diagonalize $B=S M S^{-1}$ as $$B=\left(\begin{matrix} e^{\tau} & e^{-\tau}\\ 1 & 1 \end{matrix}\right) \left(\begin{matrix} e^\tau & 0 \\ 0 & e^{-\tau}\end{matrix}\right) \left(\begin{matrix} e^{\tau} & e^{-\tau}\\ 1 & 1 \end{matrix}\right)^{-1}$$
and then some simple matrix multiplication gives \begin{align} B^N&=S M^N S^{-1}\\ &=\left(\begin{matrix} e^{\tau} & e^{-\tau}\\ 1 & 1 \end{matrix}\right) \left(\begin{matrix} e^{N\tau} & 0 \\ 0 & e^{-N\tau}\end{matrix}\right) \left(\begin{matrix} e^{\tau} & e^{-\tau}\\ 1 & 1 \end{matrix}\right)^{-1}\\ &=\frac{1}{\sinh\tau}\left(\begin{matrix} \sinh((N+1)\tau) & -\sinh(N \tau) \\ \sinh(N\tau) & -\sinh((N-1)\tau) \end{matrix}\right) \end{align}
From this we identify $a_{11}=\dfrac{\sinh((N+1)\tau)}{\sinh \tau}.$
Summing the binomial expansion
To match this to the RHS, we first define $$f_N = \sum_i (-1)^i \binom{N-i}{i}d^{N-2i}$$ where $\binom{n}{k}=C_{n}^{k}=\frac{(n+k)!}{n! k!}$; the range on $i$ is enforced by the binomial coefficient vanishing unless $0\leq k \leq n$. Then multiply both sides by a formal variable $x^N$ and sum over $N$:
\begin{align} F(x):=\sum_{N=0}^\infty f_N x^N &= \sum_{N,i} \binom{N-i}{i}(-1)^i d^{N-2i}x^N\\ &=\sum_{N,i} \binom{N+i}{i}(-1)^i d^{N}x^{N+2i} &(\,N\mapsto N+2i\,)\\ &=\sum_{i=0}^\infty \frac{(-x^2)^i}{(1-x d)^{i+1}}\\ &=\frac{(1-dx)^{-1}}{1+x^2(1-xd)^{-1}}=\frac{1}{1-dx+x^2} \end{align}
where in the third line we have made use of the negative binomial series and then summed the resulting geometric series. Then a geometric series expansion via partial fractions yields
\begin{align} F(x) &= \frac{1}{1-2 x \cosh\tau +x^2}=\frac{1}{(x-e^{\tau})(x-e^{-\tau})}\\ &= \frac{1}{e^{\tau}-e^{-\tau}}\left[\frac{1}{x-e^{\tau}}-\frac{1}{x-e^{-\tau}}\right]\\ &= \sum_{N=0}^\infty \frac{-e^{-(N+1)\tau}+e^{(N+1)\tau}}{e^{\tau}-e^{-\tau}}x^N = \sum_{N=0}^\infty \frac{\sinh((N+1)\tau)}{\sinh\tau} x^N \end{align}
Identifying coefficients of $F(x)$, we conclude that $f_N$ give the same expression as $a_{11}$ found above. This proves the relation.