How many n digit numbers you can write by using only 1's and 2's and you are allowed to use neither two consecutive 1's nor three consecutive 2's?
You don't need a computer program at all!
I'll start with doing small values by hand:
f(1)=2: 1, 2
f(2)=3: 12, 21, 22
f(3)=4: 121, 122, 212, 221
f(4)=5: 1212, 1221, 2121, 2122, 2212
f(5)=7: 12121, 12122, 12212, 21212, 21221, 22121, 22122
To go larger this is where we analyze the behavior of long strings. A 1 must be followed by either a single 2 or a pair of 2s before the next occurrence of a 1. So the body of a long string consists of building blocks of "12" or "122".
This forms a recursive method of construction. A string in f(n) can be formed by taking a a string from f(n-2) and inserting a "12" prior to the first 1, or taking a string from f(n-3) and inserting a "122" prior to the first 1.
Then the recursive formula is readily apparent: f(n) = f(n-2)+f(n-3).
As an exercise I will construct f(6) (f(3)+f(4)=9):
f(3)->f(6): 121, 122, 212, 221 -> 122121, 122122, 212212, 221221
f(4)->f(6): 1212, 1221, 2121, 2122, 2212 -> 121212, 121221, 212121, 212122, 221212.
So then the sequence f(n) for the quantity of numbers of length n as prescribed in the problem begins with 2,3,4,5,7,9,12,16,21,28,... with larger terms generated by f(n)=f(n-2)+f(n-3).
Analytic Solution
