La cantidad de subconjuntos de [tex]\lbrace1,2,3,\dots,n\rbrace[/tex] para los primeros números naturales n son:
[tex]n=1[/tex]: [tex]\lbrace1\rbrace[/tex]
[tex]n=2[/tex]: [tex]\lbrace1\rbrace[/tex], [tex]\lbrace2\rbrace[/tex]
[tex]n=3[/tex]: [tex]\lbrace1\rbrace[/tex], [tex]\lbrace2\rbrace[/tex], [tex]\lbrace3\rbrace[/tex] ,[tex]\lbrace1,3\rbrace[/tex]
[tex]n=4[/tex]: [tex]\lbrace1\rbrace[/tex], [tex]\lbrace2\rbrace[/tex], [tex]\lbrace3\rbrace[/tex], [tex]\lbrace4\rbrace[/tex], [tex]\lbrace1,3\rbrace[/tex], [tex]\lbrace1,4\rbrace[/tex], [tex]\lbrace2,4\rbrace[/tex]
[tex]\dots[/tex]
Es decir,
[tex]n=1[/tex] ----------------- [tex]1[/tex] subconjunto =[tex]1[/tex]
[tex]n=2[/tex] ----------------- [tex]2[/tex] subconjuntos =[tex]1+1[/tex]
[tex]n=3[/tex] ----------------- [tex]4[/tex] subconjuntos =[tex]1+1+2[/tex]
[tex]n=4[/tex] ----------------- [tex]7[/tex] subconjuntos =[tex]1+1+2+3[/tex]
[tex]n=5[/tex] ----------------[tex]12[/tex] subconjuntos =[tex]1+1+2+3+5[/tex]
[tex]n=6[/tex] ----------------[tex]20[/tex] subconjuntos =[tex]1+1+2+3+5+8[/tex]
[tex]\dots[/tex]
Por lo tanto, la suma de los números a la derecha corresponden a los términos de la Sucesión de Fibonacci, la cual se define como:
[tex]f_{1} = 1[/tex]
[tex]f_{2} = 1[/tex]
[tex]f_{n}[/tex]= [tex]f_{n-1}[/tex] + [tex]f_{n-2}[/tex] , [tex]\forall n>2[/tex]
Entonces, la cantidad de subconjuntos de [tex]\lbrace1,2,3,\dots,n\rbrace[/tex]que no contienen números consecutivos son:
[tex]\sum_{i=1}^{n} {f_{n}}[/tex]
Siendo[tex]f_{n}[/tex]el enésimo término de la sucesión de Fibonacci.
