Uva-10450 – World Cup Noise

Short Problem Description:

Given n. You have to output how many bit string of length n is possible so that no consecutive 1 exists. As for example, if n=3, then there are total 2^3=8 bit string possible. They are 000, 001, 010, 011, 100, 101, 110, 111. But among these 011, 110, 111 have the bit string with consecutive 1. So answer is 8-3=5.
Solution Trick:

The logic of this problem goes to Tree Diagram. Simply try to draw a tree with 0 and 1 so that no consecutive 1 remains together. Then see, the logic is just Fibonacci Series.

My Code: Click Here