Dejemos que $f(n)$ sea el número de subconjuntos de $[n]$ que no contengan dos enteros consecutivos. Por ejemplo, para $n = 4$ tenemos los subconjuntos $\emptyset$ , $\{1\}$ , $\{2\}$ , $\{3\}$ , $\{4\}$ , $\{1, 3\}$ , $\{1, 4\}$ , $\{2, 4\}$ Así que $f(4) = 8$ .
La solución: $f(n) = f(n 1) + f(n 2)$ para $n \geq 2$ .
Mi pregunta es: ¿Cómo abordar este tipo de problemas para llegar a la solución de la recurrencia?
Para ver que $f(n)=f(n-1)+f(n-2)$ , obsérvese que un subconjunto $A$ de $[n]$ que satisface la condición o bien contiene $n$ o no lo hace.
Si $n\in A$ entonces $A$ seguramente no contiene $n-1$ y por lo tanto $A-\{n\}$ es un subconjunto de $[n-2]$ satisfaciendo la condición. Por lo tanto, hay $f(n-2)$ tales conjuntos $A$ .
En caso contrario, si $n\not\in A$ entonces $A-\{n\}$ es un subconjunto de $[n-1]$ satisfaciendo la condición. Por lo tanto, hay $f(n-1)$ tales conjuntos $A$ .
En total, obtenemos $f(n)=f(n-2)+f(n-1)$ , según se desee. Dado que $f(0)=1$ et $f(1)=2$ vemos que $f(n)=F_{n+2}$ El $(n+2)$ n número de Fibonacci.
Obsérvese que para este tipo de problemas es fundamental intentar reducir el problema a uno de los casos anteriores, por ejemplo, eliminando elementos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
