Subconjuntos sin elementos consecutivos.
El problema de contar subconjuntos sin elementos adyacentes te pide encontrar el número de subconjuntos del conjunto $S = {1, 2, \dots, n}$ tales que ningún par de elementos en el subconjunto sean enteros consecutivos. Por ejemplo, si $n=4$, el subconjunto ${1, 3}$ es válido, pero ${1, 2, 4}$ no lo es porque el 1 y el 2 son consecutivos. Este concepto es un puente fundamental entre la teoría combinatoria de conjuntos y las sucesiones recursivas. Aparece seguido en competencias como el AMC y el AIME, muchas veces planteado como elegir objetos de una fila donde no puedes escoger dos que estén juntos, o seleccionar vértices no adyacentes en un grafo.
La importancia de este tema está en su conexión con la sucesión de Fibonacci. Al analizar la estructura de estos subconjuntos de forma recursiva —específicamente fijándote en si incluyes o excluyes el último elemento $n$— descubres que el conteo cumple con la relación de recurrencia de Fibonacci. Esto convierte un problema de conteo que podría ser tedioso en un cálculo simple del $k$-ésimo número de Fibonacci. Esta técnica es un caso específico de "conteo por recurrencia lineal" y sirve como un ejemplo principal de cómo resolver problemas combinatorios estableciendo una correspondencia uno a uno (biyección) con sucesiones conocidas.
Una idea clave al resolver estos