Problem:
Find the number of subsets of that contain exactly one pair of consecutive integers. Examples of such subsets are and .
Solution:
Immediately, we should think about using recursion, as it seems as though we can solve this problem over smaller subsets and "build" them together to get our answer.
Let's first create a sequence which is the number of subsets of the sequence such that there are no consecutive pairs.
Let's first build our series
First off,
Similarly, we'd have that
Recursively to build , notice that if the nth element is included in our subset, then we'd add and if the nth element is in our subset, we'd add , so we have that
Now, let's build the answer over subsets of using casework on which numbers are consecutive.
Notice if are the two consecutive numbers, we'd add to solve the problem over as 3 can not be in our subset.
Similarly, if it was we'd add
If it was , we'd add , as we are multiplying the ways to find f over the sets and \
If it was we'd similarly have , and after this they repeat by symmetry.
The only case that doesn't repeat is that would be
Adding these all up, our answer would be
which would be
The problems on this page are the property of the MAA's American Mathematics Competitions