In how many ways can n be written as the sum of positive integers with no consecutive 1's?
For example a(4)=5 because we have (4)=(1+3)=(2+2)=(3+1)=(1+2+1)
Prove the sequence defined by a(n).
Lets start by defining b(n) to be the number of ways that a natural number n can be written as the sum of positive integers with no consecutive 1's AND the last summand is bigger than 1.
Then a(n) can be created from direct copies b(n) and copies of b(n-1) with "+1" appended.
Example: b(3)=2 from (3)=(1+2) and b(4)=3 from (4)=(1+3)=(2+2)
Then a(4)=b(4)+b(3)=5 from (4)=(1+3)=(2+2) and (3+1)=(1+2+1)
b(n) is easy to recursively construct. We can take any b(n-1) sum and increment the last term, or take any b(n-2) sum and append "+2", or take any b(n-3) sum and append "+1+2"
Example: b(2)=1 from (2) b(3)=2 from (3)=(1+2) and b(4)=3 from (4)=(1+3)=(2+2)
Then incrementing each of b(4) gives (5)=(1+4)=(2+3), and appending each of b(3) gives (3+2)=(1+2+2), and appending each of b(2) gives (2+1+2)
Then b(5)=6 from a total set of (5)=(1+4)=(2+3)=(3+2)=(1+2+2)=(2+1+2)
Then the recursive construction of the sets for b(n) implies the formula is b(n)=b(n-1)+b(n-2)+b(n-3). But since a(n) = b(n)+b(n-1) we can do some manipulations to get a formula for a(n):
a(n) = b(n) + b(n-1)
= [b(n-1)+b(n-2)+b(n-3)] + [b(n-2)+b(n-3)+b(n-4)]
= [b(n-1)+b(n-2)] + [b(n-2)+b(n-3)] + [b(n-3)+b(n-4)]
= a(n-1) + a(n-2) + a(n-3)
Therefore a recursive formula to evaluate the values a(n) is a(n) = a(n-1) + a(n-2) + a(n-3). Then we just need initial values a(1)=1, a(2) = 1, and a(3)=3.
This creates the sequence 1,1,3,5,9,17,31,57,105,.... which can be found to be
OEIS A000213.
Solution
