AMC12 2006 A

This question can be solved fairly directly by casework and pattern-finding. We give a somewhat more general attack, based on the solution to the following problem: How many ways are there to choose $k$ elements from an ordered $n$ element set without choosing two consecutive members? You want to choose $k$ numbers out of $n$ with no consecutive numbers. For each configuration, we can subtract $i-1$ from the $i$-th element in your subset. This converts your configuration into a configuration with $k$ elements where the largest possible element is $n-k+1$, with no restriction on consecutive numbers. Since this process is easily reversible, we have a bijection. Without consideration of the second condition, we have: ${15 \choose 1} + {14 \choose 2} + {13 \choose 3} + ... + {9 \choose 7} + {8 \choose 8}$ Now we examine the second condition. It simply states that no element in our original configuration (and hence also the modified configuration, since we don't move the smallest element) can be less than $k$, which translates to subtracting $k - 1$ from the "top" of each binomial coefficient. Now we have, after we cancel all the terms ${n \choose k}$ where $n < k$, ${15 \choose 1} + {13 \choose 2} + {11 \choose 3} + {9 \choose 4} + {7 \choose 5}= 15 + 78 + 165 + 126 + 21 = \boxed{405} \Longrightarrow \mathrm{(E)}$