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$?
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}$