Demostración por Inducción Matemática y Resolución de Ecuaciones de Recurrencia
Clasificado en Matemáticas
Escrito el en español con un tamaño de 6,96 KB
Inducción Matemática
La inducción matemática es un método de demostración que se utiliza para probar que una proposición P(n) es verdadera para todos los números enteros n mayores o iguales a un valor inicial n0 (generalmente 0 o 1).
Pasos de la Inducción Matemática
- Base de la inducción: Se demuestra que la proposición P(n) se cumple para el valor inicial n0.
- Hipótesis de inducción: Se asume que P(k) es verdadera para algún entero k ≥ n0.
- Tesis de inducción: Se demuestra que, si P(k) es verdadera (hipótesis), entonces P(k+1) también es verdadera.
Si se cumplen estos tres pasos, se concluye que P(n) es verdadera para todos los enteros n ≥ n0.
Ejemplo 1
Demostrar que P(n) = n3 + (n+1)3 + (n+2)3 es divisible por 9 para todo n ≥ 1.
- Base: Para n=1; 13 + 23 + 33 = 1 + 8 + 27 = 36, que es divisible por 9.
- Hipótesis: Se supone que P(k) = k3 + (k+1)3 + (k+2)3 = 9m para algún entero m ≥ 1.
- Tesis: Demostrar que P(k+1) = (k+1)3 + (k+2)3 + (k+3)3 es divisible por 9.
P(k+1) = (k+1)3 + (k+2)3 + (k3 + 9k2 + 27k + 27)
P(k+1) = [k3 + (k+1)3 + (k+2)3] + 9(k2 + 3k + 3)
Por hipótesis de inducción, la expresión entre corchetes es igual a 9m. Por lo tanto:
P(k+1) = 9m + 9(k2 + 3k + 3) = 9(m + k2 + 3k + 3) = 9L, donde L es un entero.
Como P(k+1) es un múltiplo de 9, la proposición es verdadera.
Ejemplo 2
Demostrar que P(n) = n ≤ n2 para todo n ≥ 1.
- Base: P(1) = 1 ≤ 12 = 1, que es verdadero.
- Hipótesis: Se supone que P(k) = k ≤ k2 para algún k ≥ 1.
- Tesis: Demostrar que (k+1) ≤ (k+1)2.
Partiendo de la hipótesis, k ≤ k2.
Sumando (1+2k) a ambos lados: k + 1 + 2k ≤ k2 + 1 + 2k
k+1 ≤ k2 + 2k + 1 -2k +k
k+1 ≤ (k+1)2
Por lo tanto, la proposición P(n) es verdadera para todo n ≥ 1.
Ecuaciones de Recurrencia
Una ecuación de recurrencia es una ecuación que define una secuencia recursivamente: cada término de la secuencia se define en función de los términos anteriores.
Ecuaciones de Recurrencia Lineales Homogéneas con Coeficientes Constantes
La forma general es: an = c1an-1 + c2an-2 + ... + ckan-k, donde los ci son constantes.
Resolución
- Se escribe la ecuación característica: rk - c1rk-1 - c2rk-2 - ... - ck = 0.
- Se encuentran las raíces de la ecuación característica (r1, r2, ..., rk).
- La solución general depende de la naturaleza de las raíces:
- Raíces distintas: an = A1(r1)n + A2(r2)n + ... + Ak(rk)n
- Raíces repetidas (por ejemplo, r1 se repite m veces): an = (A1nm-1 + A2nm-2 + ... + Am)(r1)n + ...
- Raíces complejas conjugadas (r = α ± βi): an = rn(Acos(nθ) + Bsen(nθ)), donde r = √(α2 + β2) y θ = arctan(β/α).
Las constantes Ai, A, y B se determinan a partir de las condiciones iniciales.
Ejemplo
Resolver la ecuación de recurrencia an = 6an-1 - 9an-2 con condiciones iniciales a0 = 1 y a1 = 6.
- Ecuación característica: r2 - 6r + 9 = 0.
- Factorizando: (r - 3)(r - 3) = 0. Raíces: r1 = r2 = 3 (raíz repetida).
- Solución general: an = (An + B)(3)n.
- Usando las condiciones iniciales:
- a0 = (A(0) + B)(3)0 = B = 1.
- a1 = (A(1) + B)(3)1 = 3A + 3B = 6. Como B = 1, entonces 3A + 3 = 6, y A = 1.
- Solución final: an = (n + 1)(3)n.
Ecuaciones de Recurrencia No Homogéneas
Forma general: an = c1an-1 + c2an-2 + ... + ckan-k + f(n), donde f(n) es una función de n.
Resolución
- Se resuelve la ecuación homogénea asociada (f(n) = 0) para obtener la solución homogénea anh.
- Se encuentra una solución particular anp que dependa de la forma de f(n).
- La solución general es la suma de la solución homogénea y la solución particular: an = anh + anp.
Formas comunes de f(n) y anp
- Si f(n) es constante, se prueba con anp = A (constante).
- Si f(n) es un polinomio de grado m, se prueba con anp = un polinomio de grado m (Amnm + Am-1nm-1 + ... + A0).
- Si f(n) es de la forma C(k)n, se prueba con:
- anp = A(k)n si k no es raíz de la ecuación característica.
- anp = An(k)n si k es raíz simple de la ecuación característica.
- anp = Anm(k)n si k es raíz múltiple de multiplicidad m.
Nota: Si f(n) es una combinación de las formas anteriores, anp será una combinación similar.