Solution
No Consecutive Elements
Show the problem again
How many subsets of {1, 2, ..., 10} (including the empty set) contain no two consecutive integers?
Worked solution
The answer is 144. Let a_n count such subsets of {1, ..., n}. Either n is excluded (a_{n−1} ways) or included, forcing n−1 out (a_{n−2} ways): a_n = a_{n−1} + a_{n−2} with a₁ = 2, a₂ = 3. These are Fibonacci numbers, a_n = F_{n+2}, so a₁₀ = F₁₂ = 144.
Source: Standard Fibonacci-flavoured subset-counting exercise from combinatorics texts. Statement written for AxiomIQ.