Here is an interesting problem based on one I found in the 2008 AIME (Q11).
How many compositions of the positive integer n have adjacent parts with different parity?
For example, a valid composition of n=14 is
14 = 1 + 2 + 5 + 2 + 1 + 2 + 1,
since the 1,2,5,2,1,2,1 alternate between being odd and even.
The first terms of the sequence are (OEIS A062200)
1, 1, 3, 2, 6, 6, 11, 16, 22, 37, 49, 80, …
Interestingly the sequence decreases between n=3 and 4 since the only valid compositions of 4 are 4 = 1 + 2 + 1 and 4, while 3 = 1 + 1 + 1 = 2 + 1 = 1 + 2.
Here is the first approach I came up with to solve the problem. Let be the number of such compositions starting with an even number and let be the number of compositions starting with an odd number. We wish to find . We identify four cases:
- If is odd and the composition starts with an even number , we remove that even number and have a composition of starting with an odd number. Summing over choices of ,
- If is odd and the composition starts with an odd number , we either have the single term composition , or we remove that odd number and have a composition of starting with an even number. Summing over choices of ,
- If is even and the composition starts with an even number , we either have the single term composition , or we remove that even number and have a composition of starting with an odd number. Summing over choices of ,
- If is even and the composition starts with an odd number , we remove that odd number and have a composition of starting with an even number. Summing over choices of ,
Recursions (1)-(4) with the initial conditions allows us to generate the following table.
After writing out some terms I noticed the pattern
I later saw why this is so. Firstly, a composition of that starts with an even number can be obtained from any composition of by adding 2 to the first term if even or inserting 2 at the start if odd. Hence . For the second relation, if the composition of starts with an odd number, it either is 1 plus an even-starting composition of or it can be obtained from an odd-starting composition of by adding 2 to the first term. Hence .
From (5) and using we find that
Together with the initial terms , (6) enables us to generate our desired terms without requiring or .
The OEIS page also gives the following expression for :
Here is how to show this result, with help from the solution at AoPS here. For ease of exposition convert the problem to one of binary strings: we require the number of length-n 0-1 strings so that maximal continguous blocks of 1s have even length and maximal contiguous blocks of 0s have odd length.
Suppose there are maximal blocks of 0s. All but the last such block must necessarily be followed by a pair of 1s. That is, the string has the form
where blocks enclosed by  contain the same digit (0 or 1) and 0 or more pairs of digits are in place of the sets of four dots. We have shown blocks above but the first and last may be empty.
Let , which is the number of pairs of digits to use after 0s are used (noting that must be even). We have 0s used above along with pairs of 1s. Therefore pairs of 0s or 1s need to inserted into the blocks above. The blocks that they end up determine whether they are 0 or 1.
Now pairs can be inserted into blocks in ways, since we write out symbols in a row and choose of them to be pairs, with the remaining symbols representing separators between blocks. In our case,
, and , so
Summing over choices of gives (7) as desired. Note that some of the terms will be 0 as ranges from 0 to n+1.
For example, when n=11 and 12, we have
matching the values given in the table above.