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.
 A: Write the recursion formula $f(n)=\ldots$, and below it $f(n-1)=\ldots\ $. Subtract these two equations, and you obtain the linear difference equation
$$f(n)=2f(n-1)-f(n-2)+f(n-4)\qquad(n\geq4)\ .$$
Its characteristic equation is
$$\lambda^4-2\lambda^3+\lambda^2-1=0$$
with the solutions
$$\lambda_1={1+\sqrt{5}\over2},\quad \lambda_2={1-\sqrt{5}\over2},\quad \lambda_3=e^{i\pi/3},\quad \lambda_4=e^{-i\pi/3}\ .$$
It follows that
$$f(n)=\sum_{k=1}^4C_k \lambda_k^n$$
with certain values for the $C_k$ that can be found using the initial conditions. The result is: Consider the two sequences
$$\eqalign{g(0)&=1,\quad g(1)=1,\quad g(n):=g(n-1)+g(n-2)\ ,\cr
h(0)&=1,\quad h(1)=1,\quad h(n):=h(n-1)-h(n-2)\ .\cr}$$
The first is essentially the sequence of Fibonacci numbers, the second is periodic $(1,1,0,-1,-1,0,\ldots)$ with period $6$. Then
$$f(n)={1\over2}\bigl(g(n)+h(n)\bigr)\qquad(n\geq0)\ .$$
A: 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.
