Por qué esta recursión es la misma que la secuencia A005252 de la OEIS

Question

Tengo la recursión:

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

Así que tenemos, por ejemplo

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

Me he dado cuenta de que esta secuencia es la misma que A005252 - OEIS que se define como:

$$a(n) = \sum_{k=0..\lfloor n/4 \rfloor} \binom{n-2k}{2k}$$

No estoy seguro de cómo llegar. He intentado utilizar una función generadora, pero no estoy seguro de cómo manipularla.

Answer 1

Escribe la fórmula de recursión $f(n)=\ldots$ y debajo $f(n-1)=\ldots\ $ . Si se restan estas dos ecuaciones, se obtiene la ecuación de diferencia lineal $$f(n)=2f(n-1)-f(n-2)+f(n-4)\qquad(n\geq4)\ .$$ Su ecuación característica es $$\lambda^4-2\lambda^3+\lambda^2-1=0$$ con las soluciones $$\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}\ .$$ De ello se desprende que $$f(n)=\sum_{k=1}^4C_k \lambda_k^n$$ con ciertos valores para el $C_k$ que se puede encontrar utilizando las condiciones iniciales. El resultado es: Consideremos las dos secuencias $$\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}$$ El primero es esencialmente la secuencia de números de Fibonacci, el segundo es periódico $(1,1,0,-1,-1,0,\ldots)$ con el período $6$ . Entonces $$f(n)={1\over2}\bigl(g(n)+h(n)\bigr)\qquad(n\geq0)\ .$$

Answer 2

Dejemos que $F(z)=\sum_{n \ge 0} f_n z^n$ sea la función generadora. Entonces la relación de recurrencia implica que \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} así que $$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)},$$ que coincide con la función generadora mostrada en OEIS.