Given a number n, consider all 2ⁿ sequences of as and bs that have length n. A sequence is called a good one if and only if there are no two bs in a row anywhere in it. You have to count the total number N(n) of good sequences of length n. Design an efficient algorithm for this problem. Explain why your algorithm yields the correct solution.

For example, if n = 4, the following sequences are good: aaaa, aaab, aaba, abaa, baaa, abab, baab, baba which yields the answer N(4) = 8. Note, that you do not need to print all good sequences; the only thing you have to do is to find the number N(n).

Hints.

1. Could you use divide-and-conquer or dynamic programming?
2. Could you reduce the problem for n to the problems for i < n?
3. What characters can be at the end of a good sequence?