<s>[INST] A sequence related to squares of Fibonacci nubers Let $f(n)$ be defined by
$f(n)=f(n-1)+f(n-3)+f(n-4)$, for $n \ge 5$, 
$f(1)=1, f(2)=1, f(3)=2, f(4)=4$.
First few terms of the sequence $(f(1), f(2), f(3), \ldots$) look like
$(1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, \ldots)$
Here we recognize that the subsequence consisting of even numbered terms looks like 
$(f(2), f(4), f(6), f(8), f(10), f(12), \ldots)=(1^2, 2^2, 3^2, 5^2, 8^2, 13^2, \ldots)$
which tells that 
$f(2k)=F_{k+1}^2$ for $k=1, 2, 3, 4, 5, 6$, where $F_k$ stands for the $n$th Fibonacci number. 
Does this hold for all $k=1, 2, \ldots$?
 [/INST] This is simple to solve, surprisingly. Define $g(z) = \sum_{n \ge 0} f(n) z^n$,
shift indices to get:
$\begin{align}
f(n + 4)
 = f(n + 3) + f(n + 1) + f(n)
\end{align}$
Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$\begin{align}
\frac{g(z) - f(0) - f(1) z - f(2) z^2 - f(3) z^3}{z^4}
  = \frac{g(z) - f(0) - f(1) z - f(2) z^2}{z^3}
       + \frac{g(z) - f(0)}{z}
       + g(z)
\end{align}$
Running the recurrence backwards gives $f(0) = 1$. With the initial values we can solve for $g(z)$:
$\begin{align}
g(z)
  &= \frac{1}{1 - z - z^3 - z^4} \\
  &= \frac{3 + z}{5 (1 - z - z^2)}
       - \frac{2 + z}{5 (1 + z^2)}
\end{align}$
The Fibonacci numbers are defined by:
$\begin{align}
F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1
\end{align}$
Their generating function is:
$\begin{align}
F(z) = \frac{z}{1 - z - z^2}
\end{align}$
The generating function for the sequence $F_{n + 1}$ is just:
$\begin{align}
\frac{F(z) - F_0}{z}
  = \frac{1}{1 - z - z^2}
\end{align}$
This gives the first term. For the second one:
$\begin{align}
\frac{2 + z}{1 + z^2}
  &= \frac{2 - \mathrm{i}}{2} \cdot \frac{1}{1 - \mathrm{i} z}
       + \frac{2 + \mathrm{i}}{2} \cdot \frac{1}{1 + \mathrm{i} z}
\end{align}$
Note that the coefficients are complex conjugates, so that:
$\begin{align}
[z^n] \frac{2 + z}{5 (1 + z^2)}
  &= 2 \Re\left( \frac{2 - \mathrm{i}}{10} \cdot \mathrm{i}^n \right) \\
  &= \frac{\sqrt{5}}{5}
       \Re\left(\exp\left(\arctan(1/2) \mathrm{i}\right)
                  \cdot \exp\left(\frac{\pi n \mathrm{i}}{2}\right)
          \right) \\
  &= \frac{\sqrt{5}}{5}
       \cos\left(\frac{\pi n}{2} + \arctan\left( \frac{1}{2}\right)\right)
\end{align}$
Pulling all together:
$\begin{align}
f(n) = \frac{3}{5}  F_{n + 1} + \frac{1}{5} F_n
          + \frac{\sqrt{5}}{5}
               \cos\left(
                     \frac{\pi n}{2} + \arctan\left( \frac{1}{2}\right)
                   \right)
\end{align}$
</s>