What is the number of subsets of $\{1,...,n\}$ that contain at least one of any two consecutive elements? This is a weird question. I don't really understand the "at least one of two consecutive elements" part. I think those are such sets:
$\{1,3,5,7,9\}, \{2,4,6,8,10\}, \{1,2,3,4,5,6,7,8,9,10\}$
Are there any other subsets like these?
 A: Hint: Every subset of $[n]$ that fulfills your criteria must have either $n-1$ or $n$ as it's largest element.
Hint: How would you create a subset of $[n+1]$? What can you say about the largest element?
Hint Let $G_n$ be the answer. Use the above to show that $G_{n+1} = G_n + G_{n-1}$. 

 Consider any valid subset, and split it according to the largest element in the subset.
If the largest element is $n+1$, then ignoring this element, we have a valid subset for $G_n$.
If the largest element is $n$, then ignoring this element, we have a valid subset for $G_{n-1}$.
Hence $G_{n+1} = G_{n} + G_{n-1}$

A: Here are some other examples of subsets of $\{1,...,10\}$ containing one of any two consecutive elements: $\{1,2,3,5,6,8,10\},\{2,4,6,7,9\}$. Another way to think of these sets is as those with no gaps bigger than $1$. This interpretation may help you begin to count them: either $1$ or $2$ is in the set, and if $k$ is in then either $k+1$ or $k+2$ must be, so you can define a set by the differences between its consecutive elements.
A: The sets you want to count correspond to sequences of $n$ zeros and ones that don't contain two consecutive zeros.  The counts are given by the Fibonacci numbers; see http://en.wikipedia.org/wiki/Fibonacci_number specifically the first bullet item under "Occurrences in Mathematics" (and interchange the roles of $0$ and $1$)>
