Why this recursion is the same as OEIS sequence A005252

Question

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.

Answer 1

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.

Answer 2

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)\ .$$