Forma cerrada para $F(n) = \sum_{i=1}^k F(n-i)$

Question

Si tenemos $F(n) = F(n-1) + F(n-2)$ y $F(0) = 0$ y $F(1) =1$ entonces obtenemos el Secuencia de Fibonacci . Una solución de forma cerrada es:

$$ F_n = \left[\frac{\left(\frac{1+\sqrt{5}}{\sqrt{5}}\right)^n}{\sqrt{5}}\right] ,$$

donde $[]$ redondea al número entero más cercano.

¿Qué obtenemos como solución de forma cerrada para $F(n) = \sum_{i=1}^3 F(n-i)$ con $F(0) = 1, F(1) = 2, F(2) = 4$ ?

En general, si establecemos $F(i) = a_i$ para $i \in \{0,\dots,k-1\}$ , $a_i \geq 0$ y constante $k >1$ ¿qué hace la forma cerrada de la solución de forma cerrada para $F(n) = \sum_{i=1}^k F(n-i)$ para los grandes $n$ ?

Answer 1

Ejemplo:

$F(n)=F(n-1)+F(n-2)\enspace $ con un $\enspace F(0)\enspace $ y $\enspace F(1)$

$x^n=x^{n-1}+x^{n-2}\enspace$ significa $\enspace x^2=x^1+x^0\enspace$ => $\enspace x\in\{x_1,x_2\}$

$F(n):=ax_1^n+bx_2^n$

Sistema de ecuaciones lineales: $\enspace ax_1^0+bx_2^0=F(0) \enspace $ y $\enspace ax_1^1+bx_2^1=F(1)$

De ello se desprende $\,a\,$ y $\,b\,$ y por lo tanto $\,F(n)$ .

Nota: Ahora ya sabes cómo resolver la general $k\,$ (arriba: $\,k=2$ ) .

Answer 2

La solución tiene una dificultad algebraica creciente porque una forma cerrada está ligada a las raíces de una ecuación de grado $n$ al igual que en la secuencia de Fibonacci hay que resolver $x^2-x-1=0$ para su pregunta $F(n) = \sum_{i=1}^3 F(n-i)$ necesitas resolver $ z^3-z^2-z-1=0$ . Dos raíces son números complejos y la solución general es bastante fea

Para $n>4$ , como sabes, en general no hay forma de encontrar raíces por radicales pero el aspecto es siempre similar a la forma cerrada de Fibonacci. Raíces de ecuaciones polinómicas elevadas a $n$ y sumados

Una forma aproximada que funciona muy bien es

$f(n)\approx -(0.0687258\, -0.123522 i) (-0.419643+0.606291 i)^n+(-0.0687258-0.123522 i) (-0.419643-0.606291 i)^n+1.13745\cdot 1.83929^n$

que da los primeros términos

$1,\;2,\;4,\;7,\;13,\;24,\;44,\;81,\;149,\;274,\;504,\;927,\;1705,\;3136,\;5768,\;10609,\;19513,\;35890,\;66012,\;121415,\;223317,\ldots$