Why is $ \frac{5}{64}((161+72\sqrt{5})^{-n}+(161+72\sqrt{5})^{n}-2)$ always a perfect square?

Let $a=9+4\sqrt{5}$, then $$f(n) = {5\over 64}(a^n-a^{-n})^2$$

Now let $$b_n = {\sqrt{5}\over 8}(a^n-a^{-n})$$

so it is enought to prove that every $b_n$ is an integer. This can be done easly if you write a recursive formula for $b_n$:

$$b_{n+1}= 18b_n-b_{n-1}$$ where $b_0=0$ and $b_1=5$ and prove that fact with induction.

It's $$\frac{5}{64}\left((9+4\sqrt5)^{2n}+(9+4\sqrt5)^{-2n}-2\right)=\frac{5}{64}\left((9+4\sqrt5)^n-(9-4\sqrt5)^n\right)^2.$$ Can you end it now?

Note that $161+72\sqrt{5} = (161-72\sqrt{5})^{-1}$ and $161+72\sqrt{5}=(9+4\sqrt{5})^2,$ and therefore \begin{align*} \big(161+72\sqrt{5}\big)^{-n}+\big(161+72\sqrt{5}\big)^{n}-2 &= \big( (161+72\sqrt{5})^{n/2} - (161-72\sqrt{5})^{n/2} \big)^2 \\ &= \big( (9+4\sqrt{5})^n - (9-4\sqrt{5})^n \big)^2. \end{align*} It therefore suffices to prove that $(9+4\sqrt{5})^n - (9-4\sqrt{5})^n$ is always $\sqrt5$ times an integer that is a multiple of $8$, which can be done using the binomial expansions of $(9\pm 4\sqrt{5})^n$.