Aquí hay dos formas posibles de obtener su respuesta.
Uno determina la solución de forma cerrada a la relación de recurrencia, y el otro toma parte de la secuencia, la relaciona con otra secuencia y usa esa relación para resolver el término específico deseado.
Antes de entrar en cualquiera de estos métodos, debemos descubrir la relación de recurrencia de esta secuencia de sumas.
¿Cuántas adiciones están involucradas en el cálculo de S0 y S1? 0 para ambos, ya que son valores predefinidos. ¿Qué hay de S2? 1 adicional.
Con un poco de inducción matemática, podemos demostrar que:
[matemáticas] S_ {n} = S_ {n-1} + S_ {n-2} + 1 [/ matemáticas]
De manera intuitiva, podemos justificar esto diciendo que S2 = S1 + S0 + 1, donde se suma el 1 debido a la suma de las dos sumas, y las dos sumas representan las sumas requeridas para generar esas sumas individuales, por lo tanto, tenemos el total Número de adiciones.
- ¿Qué problemas originalmente se pensaban que solo podían resolverse con una computadora pero luego tenían una prueba de papel y lápiz?
- ¿Cuáles son algunos conceptos en el cálculo lambda que es bueno saber antes de aprender programación funcional?
- ¿Qué tan importante es que un lenguaje de programación sea Turing completo?
- ¿Cuál es el problema P vs. NP y por qué es tan importante?
- Int a [6] = {1,2,4,5,}; ¿Es correcta esta afirmación en el concepto de matrices?
Bien, entonces nuestra relación de recurrencia está definida por lo anterior, junto con los casos base de S0 y S1.
Observación:
Por simplicidad de hacer una tabla, definamos T (n) = Sn.
T (0) = 0 F (0) = 0
T (1) = 0 F (1) = 1
T (2) = 1 F (2) = 1
T (3) = 2 F (3) = 2
T (4) = 4 F (4) = 3
T (5) = 7 F (5) = 5
T (6) = 12 F (6) = 8
T (7) = 20 F (7) = 13
T (8) = 33 F (8) = 21
T (9) = 54 F (9) = 34
T (10) = 88 F (10) = 55
T (11) = 143 F (11) = 89
T (12) = 232 F (12) = 144
T (13) = 376 F (13) = 233
F (14) = 377
De acuerdo, podemos observar que F (n + 1) = T (n) +1 de esta tabla relativamente corta.
Por lo tanto:
[matemáticas] S_ {25} = F (26) -1 = 121393-1 = 121392 [/ matemáticas]
Si eso no es tan riguroso como quisiera, existen técnicas matemáticamente rigurosas para resolver la relación de recurrencia y dar una solución de forma cerrada para calcular Sn (principalmente la sección “Generar funciones” de Cómo resolver relaciones de recurrencia).
