An alphabet with two letters A and B has rules for creating words:
1. Any A must be part of a string containing an even number of A's.
2. Any B must be part of a string of containing an odd number of B's.
For example two six letter words could be BBBAAB and AAAAAA but ABABBB would not be valid.
How many valid 15 letter words are there?
Lets start by calling T(n) the number of words of length n. And divide that into two parts: A(n) for the words ending in 'A' and B(n) for the words ending in 'B'.
We build the words recursively. For A(n) we can append 'AA' to any word from A(n-2) and B(n-2). For B(n) we can append 'B' to any word from A(n-1) or 'BB' to any word from A(n-2). This gives us a double recursion:
A(n) = A(n-2) + B(n-2)
B(n) = A(n-1) + B(n-2)
Now subtract those equations and simplify a bit to get:
B(n) = A(n) + A(n-1) - A(n-2)
Now substitute back into the first equation to get:
A(n) = 2*A(n-2) + A(n-3) - A(n-4).
We can get a formula for B(n) similarly, but we just need to reindex the first equation from n to n+1. Then the double recursion looks like:
A(n+1) = A(n-1) + B(n-1)
B(n) = A(n-1) + B(n-2)
Again, subtract and simplify to get:
A(n+1) = B(n) + B(n-1) - B(n-2)
And then substitute back into the second equation (reindexing n to n-2) to get:
B(n) = 2*B(n-2) + B(n-3) - B(n-4).
The two recursive formulas for A(n) and B(n) are the same, therefore T(n) = 2*T(n-2) + T(n-3) - T(n-4). Now all we need are the initial terms.
The only valid one letter word is "B" so T(1) = 1.
The only valid two letter word is "AA" so T(2) = 1.
The valid three letter words are "AAB", "BAA" and "BBB", so T(3)=3.
The valid four letter words are "AAAA" and "BAAB", so T(4)=2.
This fully defines the recursive formula for T(n). A very simple program can quickly compute T(15)=257.
Analytic Solution
