¿Cómo calcular la forma explícita de una función recursiva?

Question

que tienen esta función recursiva:

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
f(1) = 2 
f(2) = 8 

sé por experiencia que forma explícita de que sería:

f(n) = 3^n - 1 // pow(3, n) - 1 

Quiero saber si hay alguna manera de probar que. Busqué en Google un poco, pero no encontré nada simple de entender. Ya sé que las funciones de generación probablemente lo resuelven, son demasiado complejas, prefiero no entrar en ellas. Estoy buscando una manera más simple.

P.S. Si ayuda Recuerdo algo como esto resuelto:

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
// consider f(n) = x^n 
x^n = 2 * x^(n-1) + 3 * x^(n-2) + 4 

y X, entonces de alguna manera calculada que conducen a la forma explícita de la fórmula recursiva, sin embargo no puedo recordar bien

Answer 1

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
f(n+1) = 2 * f(n) + 3 * f(n-1) + 4 

f(n+1)-f(n) = 2 * f(n) - 2 * f(n-1) + 3 * f(n-1) - 3 * f(n-2) 
f(n+1) = 3 * f(n) + f(n-1) - 3 * f(n-2) 

Ahora, el 4 se ha ido. Como ha dicho el siguiente paso es dejar que f (n) = x^n

x^(n+1) = 3 * x^n + x^(n-1) - 3 * x^(n-2) 

dividir por x^(n-2)

x^3 = 3 * x^2 + x - 3 
x^3 - 3 * x^2 - x + 3 = 0 

factorizar para encontrar x

(x-3)(x-1)(x+1) = 0 
x = -1 or 1 or 3 

f(n) = A * (-1)^n + B * 1^n + C * 3^n 
f(n) = A * (-1)^n + B + C * 3^n 

Ahora encuentre A, B y C usando los valores que tiene

f(1) = 2; f(2) = 8; f(3) = 26 

f(1) = 2 = -A + B + 3C 
f(2) = 8 = A + B + 9C 
f(3) = 26 = -A + B + 27C 

solución para A, B y C:

f(3)-f(1) = 24 = 24C  => C = 1 
f(2)-f(1) = 6 = 2A + 6 => A = 0 
2 = B + 3     => B = -1 

Finalmente

f(n) = 3^n - 1 

Answer 2

En general, hay no es un algoritmo para convertir una forma recursiva en una iterativa. Este problema es indecidible. Como ejemplo, considerar esta definición de función recursiva, que define la secuencia de Collatz:

f(1) = 0 
f(2n) = 1 + f(n) 
f(2n + 1) = 1 + f(6n + 4) 

No se sabe si o no este es aún una función o no bien definido. Si existiera un algoritmo que pudiera convertirlo en una forma cerrada, podríamos decidir si estaba bien definido o no.

Sin embargo, para muchos casos comunes, es posible convertir una definición recursiva en una iterativa. El excelente libro de texto Concrete Mathematics dedica gran parte de sus páginas a mostrar cómo hacerlo. Una técnica común que funciona bastante bien cuando se tiene una suposición de cuál es la respuesta es usar la inducción. Como ejemplo para su caso, suponga que cree que su definición recursiva realmente da 3^n - 1. Para probar esto, intente probar que es verdadero para los casos base, luego demuestre que este conocimiento le permite generalizar la solución hacia arriba . No pusiste un caso base en su puesto, pero estoy asumiendo que

f(0) = 0 
f(1) = 2 

Ante esto, vamos a ver si su corazonada es correcta. Para las entradas específicas de 0 y 1, puede verificar por inspección que la función calcula 3^n - 1. Para el paso inductivo, supongamos que para todos n '< n que f (n) = 3^n - 1 . Entonces tenemos que

f(n) = 2f(n - 1) + 3f(n - 2) + 4 
    = 2 * (3^{n-1} - 1) + 3 * (3^{n-2} - 1) + 4 
    = 2 * 3^{n-1} - 2 + 3^{n-1} - 3 + 4 
    = 3 * 3^{n-1} - 5 + 4 
    = 3^n - 1 

Así que sólo han demostrado que esta función recursiva produce de hecho 3^n - 1.

Answer 3

Ok, sé que no quería generar funciones (GF partir de ahora) y todas las cosas complicadas, pero mi el problema resultó ser no lineal y los métodos lineales simples no parecían funcionar. Entonces, después de un día completo de búsqueda, encontré la respuesta y espero que estos hallazgos sean de ayuda para otros.

Mi problema: a [n + 1] = a [n]/(1 + a [n]) (es decir, no lineal (ni polinómico), pero tampoco completamente no lineal - es una ecuación de diferencia racional)

1. si su recurrencia es lineal (o polinómica), wikihow tiene instrucciones paso a paso (con y sin GF)
2. si quieres leer algo sobre GF, ir a this wiki, pero no lo hice obtenerlo hasta que comencé a hacer ejemplos (ver siguiente)
3. GF usage example en Fibonacci
4. si el ejemplo anterior no tiene sentido, descargue GF book y lea el ejemplo más simple de GF (sección 1.1, es decir, a [n + 1] = 2 a [n] +1, luego 1.2, a [n + 1] = 2 a [n] +1, luego 1.3 - Fibonacci)
5. (mientras estoy en el tema del libro) templatetypedef mencionó Concrete Mathematics, descargue here, pero no sé mucho sobre él excepto que tiene una recurrencia, sumas, y capítulo GF (entre otros) y una tabla de GF simples en la página 335
6. mientras navego más profundo para cosas no lineales, vi this page, con el cual fallé en el enfoque de z-transformaciones y no intenté el álgebra lineal, pero enlace a la diferencia racional eqn fue el mejor (ver el siguiente paso)
7. de acuerdo con this page, las funciones racionales son bueno porque puedes transformarlos en polinomios y usar métodos lineales del paso 1. 3. y 4. de arriba, que escribí a mano y probablemente cometí algún error, porque (ver 8)
8. Mathematica (o incluso el WolframAlpha gratis)) tiene un solucionador de recurrencia, que con RSolve[{a[n + 1] == a[n]/(1 + a[n]), a[1] == A}, a[n], n] me consiguió un simple {{a[n] -> A/(1 - A + A n)}}. Así que supongo que volveré y buscaré un error en los cálculos a mano (son buenos para entender cómo funciona todo el proceso de conversión).

De todos modos, espero que esto ayude.