¿Cuál es el número de subconjuntos de $\{1,...,n\}$ que contienen al menos uno de dos elementos consecutivos?

Question

Esta es una pregunta extraña. Realmente no entiendo el "por lo menos uno de dos elementos consecutivos" parte. Yo creo que son estos conjuntos:

$\{1,3,5,7,9\}, \{2,4,6,8,10\}, \{1,2,3,4,5,6,7,8,9,10\}$

¿Hay cualquier otros subconjuntos como estas?

Answer 1

Sugerencia: Cada subconjunto de $[n]$ que cumple con sus criterios debe tener $n-1$ o $n$ como el mayor elemento.

Sugerencia: ¿Cómo crear un subconjunto de a $[n+1]$? ¿Qué se puede decir sobre el elemento más grande?

Sugerencia Deje $G_n$ ser la respuesta. Usar lo anterior para mostrar que $G_{n+1} = G_n + G_{n-1}$.

Considere la posibilidad de cualquier válido subconjunto, que se dividió según el elemento más grande en el subconjunto.
Si el elemento mayor es $n+1$, después hacer caso omiso de este elemento, tenemos una válida subconjunto de $G_n$.
Si el elemento mayor es $n$, después hacer caso omiso de este elemento, tenemos una válida subconjunto de $G_{n-1}$.
Por lo tanto $G_{n+1} = G_{n} + G_{n-1}$

Answer 2

Aquí están algunos otros ejemplos de subconjuntos de $\{1,...,10\}$ que contienen uno de dos elementos consecutivos: $\{1,2,3,5,6,8,10\},\{2,4,6,7,9\}$. Otra forma de pensar de estos conjuntos es como los no vacíos más grandes que $1$. Esta interpretación puede ayudar a empezar a contar: o $1$ $2$ es en el conjunto, y si $k$ en aquel entonces o $k+1$ o $k+2$ debe ser, así se puede definir un conjunto por las diferencias entre sus elementos consecutivos.

Answer 3

Los conjuntos que desea contar corresponden a secuencias de $n$ ceros y unos que no contienen dos ceros consecutivos. Las cuentas están dados por los números de Fibonacci; Ver http://en.wikipedia.org/wiki/Fibonacci_number especialmente el primer punto de bala bajo "Ocurrencias en matemáticas" (y el intercambio de los roles de $0$ y $1$)>