Why this recursion is the same as OEIS sequence A005252 I have the recursion:
$$\left\{ \begin{array}{l}
  f(0) = f(1) = f(2) = f(3) = 1\\
  f(n) = f(n - 1) + 1 + \sum_{i = 1}^{n - 4}f(i) \text{ if $n \geqslant 4$}
\end{array} \right.$$
So we have e.g.
$$\begin{array}{lll}
  f(4) & = & f(3) + 1 = 2\\
  f(5) & = & f(4) + 1 + f(1) = 2 + 1 + 1 = 4\\
  f(6) & = & f(5) + 1 + f(2) + f(1) = 4 + 1 + 1 + 1 = 7\\
  \ldots &  & 
\end{array}$$
I noticed this sequence is the same as A005252 - OEIS, which is defined as:
$$a(n) = \sum_{k=0..\lfloor n/4 \rfloor} \binom{n-2k}{2k}$$
I'm not sure how to get there? I tried to use a generating function, but not sure how to manipulate it.

Let $F(z)=\sum_{n \ge 0} f_n z^n$ be the generating function.  Then the recurrence relation implies that
\begin{align}
F(z) 
&= \sum_{n=0}^3 1 z^n + \sum_{n \ge 4} \left(f_{n - 1} + 1 + \sum_{i = 1}^{n - 4}f_i\right)z^n \\
&= \sum_{n\ge 0} z^n + z \sum_{n \ge 4} f_{n - 1}z^{n-1} + \sum_{i \ge 1} f_i  \sum_{n\ge i+4} z^n \\
&= \frac{1}{1-z} + z \left(F(z)-\sum_{n=0}^2 f_n z^n\right) + \sum_{i \ge 1} f_i \frac{z^{i+4}}{1-z} \\
&= \frac{1}{1-z} + z F(z)-z\sum_{n=0}^2 z^n + \frac{z^4}{1-z}\left(F(z)-1\right), \\
\end{align}
so
$$F(z)=\frac{\frac{1}{1-z} -z(1+z+z^2) - \frac{z^4}{1-z}}{1-z- \frac{z^4}{1-z}}
=\frac{1-z}{(1-z+z^2)(1-z-z^2)},$$
which matches the generating function shown in OEIS.
