Explicación de la función recursiva

Question

Dada es una función $f(n)$ con:
$f(0) = 0$
$f(1) = 1$
$f(n) = 3f(n-1) + 2f(n-2)$ $\forall n2$

Me preguntaba si también hay una forma no recursiva de describir la misma función.

WolframAlpha me dice que hay uno:
$$g(n) = \frac{(\frac{1}{2}(3 + \sqrt{17}))^n - (\frac{1}{2}(3 - \sqrt{17}))^n}{\sqrt{17}}$$

Sin embargo, no tengo la menor idea de cómo determinar esta función, especialmente el $\sqrt{17}$ no tiene sentido para mí.

¿Alguien podría explicar por qué $f(n)$ et $g(n)$ son los mismos?

Answer 1

$$\begin{align} f(n) &= 3\,f(n-1) + 2\,f(n-2) \\ f(n-1) &= 1\,f(n-1) + 0\,f(n-2)\end{align}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n - 1) \\ f(n - 2) \end{bmatrix}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n - 1} \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$$

$$\begin{bmatrix} f(n + 1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

Diagonalice (encuentre los valores propios / vectores propios) y tendrá su forma cerrada.

$$\begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix} \begin{bmatrix} \frac{3 - \sqrt{17}}{2} & 0 \\ 0 & \frac{3 + \sqrt{17}}{2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix}^{-1} $$

Answer 2

Podrías demostrar que la fórmula es correcta, por inducción. Se trata de demostrar que la expresión dada satisface las condiciones iniciales y la recurrencia.

También existe una teoría general de las ecuaciones en diferencias lineales homogéneas con coeficientes constantes. Dice, para las ecuaciones en diferencia de segundo orden (nuestro caso), que si la recurrencia es $f(n)=pf(n-1)+qf(n-2)$ para hacer esto.

1) Resuelve la ecuación $x^2-px-q=0$ .

2) Si las raíces son distintas, digamos $\alpha$ et $\beta$ entonces las soluciones de la ecuación en diferencia vienen dadas por $$f(n)=A\alpha^n+B\beta^n.$$ Las constantes $A$ et $B$ se puede determinar utilizando los "valores iniciales" $f(0)$ et $f(1)$ .

Answer 3

Esto se llama una recurrencia lineal. Resolverlas es bastante sencillo, y se explica aquí: http://en.wikipedia.org/wiki/Linear_recurrence#Solving .

Lo más importante es que si $f_1$ et $f_2$ son soluciones de esta recurrencia, entonces $f_1 + f_2$ también lo es (salvo las condiciones iniciales).

El truco consiste en suponer que existe una solución de la forma $f = cr^n$ y ver a dónde te lleva.

Vamos a ver cómo funciona: $f(n) = 3f(n-1) + 2f(n-2)$ \

$cr^n = 3cr^{n-1} + 2cr^{n-2}$

Dividiendo todo por $cr^{n-2}$ y la reorganización da: $r^2 - 3r - 2 = 0$ . Factor, para conseguir: $\frac{-1}{4} \left(-2 r+\sqrt{17}+3\right) \left(2 r+\sqrt{17}-3\right) = 0$

Concluyo que $r = r_1 = \frac{\sqrt{17}-3}{2}$ o $r = r_2 = \frac{-\sqrt{17}+3}{2}$ .

Utilizando el hecho de que puedo sumar soluciones y seguir teniendo una solución a la relación de recurrencia, escribiré: $f(n) = c_1r_1^n + c_2r_2^n$

A partir de aquí, puedes introducir las condiciones iniciales para resolver $c_1$ et $c_2$ .

Answer 4

Utilizar funciones generadoras. Definir $F(z) = \sum_{n \ge 0} f(n) z^n$ , escriba la recursión como: $$ f(n + 2) = 3 f(n + 1) + 2 f(n) $$ Multiplicar por $z^n$ , suma sobre $n \ge 0$ y reconocer las sumas resultantes: $$ \frac{F(z) - f(0) - f(1) z}{z^2} = 3 \frac{F(z) - f(0)}{z} + 2 F(z) $$ Con los valores iniciales se obtiene: $$ F(z) = \frac{z}{1 - 3 z - 2 z^2} $$ Dividir en fracciones parciales y leer los coeficientes mediante series geométricas.

Answer 5

Hay múltiples métodos disponibles, véase también esta página de wikipedia .

Función generadora
En general, el método de generación de funciones es muy potente y permite resolver muchas relaciones recurrentes. Sin embargo, el método es un poco abstracto y requiere muchos cálculos propensos a errores, por lo que para una relación recurrente simple (homogénea) probablemente quieras algo más sencillo. Vea esto libro electrónico gratuito para obtener más información (probablemente baste con ver algunos ejemplos en el primer capítulo para hacerse una idea de la técnica general.

El método de los coeficientes indeterminados
En el que suponemos una solución de la forma $c^n$ . Esto nos lleva a una ecuación cuadrática para la que esperamos encontrar dos soluciones diferentes, de modo que podamos hacer una combinación lineal de las dos que satisfaga las condiciones de contorno. Si sólo hay una solución (con multiplicidad 2) de la ecuación cuadrática, hay que utilizar el hecho de que la derivada de la cuadrática es 0 también (no recuerdo los detalles, pero no es realmente relevante ahora, sólo quiero señalar que este método no siempre funciona).

El método de los valores propios
Esto funciona de la siguiente manera: escribir la relación de recurrencia en forma de matriz y encontrar los valores y vectores propios de la matriz. Cuando los hayamos encontrado, podremos escribir las condiciones iniciales como una combinación lineal de vectores propios. Ahora podemos deducir la solución de la relación de recurrencia. Supongamos que las condiciones iniciales son $x_0 = av_1 + bv_2$ et $\lambda_1, \lambda_2$ son los valores propios de $v_1, v_2$ . Entonces la solución de la relación recurrente es $x_n = a\lambda_1^nv_1 + b\lambda_2^nv_2$ . Con este método, también es posible ver por qué funciona el método de Hero para aproximar las raíces cuadradas (y con un poco de análisis, incluso se puede llegar a un método mejor para calcular las raíces cuadradas de los enteros $n$ donde $n > 2$ ).

El método de los coeficientes indeterminados es probablemente el más fácil de utilizar.