¿Cómo resolver esta relación de recurrencia?

Question

Hay una rana que podría subir 1 escalera o 3 escaleras de un tirón. ¿De cuántas maneras podría llegar a la 100ª escalera?

Se me ocurrió la solución $g(n) = g(n-3) + g(n-1)$ , donde $g(0)=g(1)=g(2)=1$ y $g(3)=2$ . Pero para resolver $g(100)$ es bastante difícil si utilizo el método de sustitución, así que sólo quiero saber si hay un método factible para resolver $g(100)$ ?

Answer 1

Como una forma posiblemente más eficiente de obtener la respuesta, propongo lo siguiente (sólo requiere aritmética de números enteros, y AFAICT al menos asintóticamente menos operaciones que la suma de coeficientes binomiales de Marvis). Podemos convertir la fórmula de recurrencia en una ecuación matricial. Definir el vector $\vec{g}(n)=(g(n),g(n+1),g(n+2))$ . Entonces $\vec{g}(n+1)=\vec{g}(n)A$ , donde $A$ es el $3\times3$ matriz $$ A=\left(\begin{array}{ccc}0&0&1\\1&0&0\\0&1&1\end{array}\right). $$ Una inducción obvia muestra que $\vec{g}(n)=A^n\vec{g}(0)$ . Ya has calculado que $\vec{g}(0)=(1,1,1)$ por lo que "todo" lo que tenemos que hacer es calcular $A^{100}$ (en realidad $A^{98}$ sería suficiente, pero eso no importa esta vez). En este caso, hay que utilizar el siempre útil algoritmo de cuadrar y multiplicar: La repetición del cuadrado te da $A^2$ , $A^4=(A^2)^2$ , $A^8$ , $\ldots$ , $A^{64}$ después de seis multiplicaciones de la matriz. Tres multiplicaciones matriciales más (un total de nueve) le dan entonces $$ A^{100}=A^{64+32+4}=A^{64}\cdot A^{32}\cdot A^4. $$

Answer 2

Esencialmente, necesitas encontrar el número de pares de números naturales $(a,b)$ tal que $$a+3b = 100$$ Y lo que es más importante, hay que tener en cuenta el orden en que $1$ y $3$ Aparece el . Por ejemplo, $a=1, b=33$ es una solución a lo anterior. Y podemos elegir $1$ un paso y $33$ tres pasos en $34$ maneras. Si la solución es $(100-3b,b)$ el número de formas que podemos tener $100-3b$ un paso y $b$ tres pasos es $$\dfrac{(100-2b)!}{b! (100-3b)!}$$ Por lo tanto, el número total de vías es $$\sum_{b=0}^{33} \dfrac{(100-2b)!}{b! (100-3b)!}$$ En general, $$g(n) = \sum_{n=0}^{\lfloor n/3 \rfloor} \dfrac{(n-2b)!}{b! (n-3b)!}$$ A partir de esto, obtenemos $g(100) = 24382819596721629$ .

EDITAR

Esto también coincide con OEIS A000930 , la secuencia de las vacas de Narayana.

Answer 3

La función generadora ordinaria de la secuencia $g(n)$ es $$ G(x) = \sum_{n=0}^\infty g(n)\,x^n = 1 + x + x^2 + 2x^3 + \cdots $$

La relación $g(n) = g(n - 1) + g(n - 3)$ conduce a la ecuación $$ G(x) - 1 - x - x^2 = x \big( G(x) - 1 - x \big) + x^3 G(x), $$ que se simplifica a $$ G(x) = \frac{1}{1 - x - x^3}. $$ Utilizar la tecnología para ampliar la serie y encontrar el $100$ de la semana, $$ g(100) = \frac{G^{(100)}(0)}{100!} = 24\,382\,819\,596\,721\,629 \approx 2.4 \times 10^{16}. $$

Answer 4

Esto es OEIS A000930 , a veces conocida como la secuencia de las vacas de Narayana. El enlace da una forma cerrada:

$$g(n)=\left\lfloor dc^n+\frac12\right\rfloor\;,$$

donde $c$ es la raíz real de $x^3-x^2-1$ y $d$ es la raíz real de $31x^3-31x^2+9x-1$ . También dice que $d=0.611491991950812\dots$ y

$$c=\frac23\cos\left(\frac13\arccos\left(\frac{29}2\right)\right)+\frac13=1.46557123187676\dots\;,$$

pero necesitará una aritmética de moderada precisión para obtener un valor exacto de $g(100)$ de eso.