Binary words.

for n=1 : 0 and 1 are two possible binary words

for n=2 onwards

suppose 1st digit is 0 then the nextr digit can be 0 or 1 (2 cases)

suppose 1st digit is 1 then next digit must be 0 (since two consecutive 1's can't occur)

so as n increases every 0 will produce 2 cases and every 1 will produce 1 case

for n=1 : 2 cases

for n=2 : 3 cases

for n=3 : 5 cases

for n=4 : 8 cases

it is becoming a fibonacci series

\frac{(1+\sqrt{5} )^{n+2}-(1-\sqrt{5} )^{n+2}}{2^{n+2}\sqrt{5}}

You won't call that a proof by looking at a few cases for n, will you? It must be proved for an arbitrary n.

in other words, how can you prove that the recursion formula of fibonacci is applicable in this situation too?

Actually it was kind of a hint or you may say half of the solution and i left for others to try and arrive till final step

by proceeding as shown in diagram above suppose for r digit 'x_r' number of zeros are available and 'y_r' no. of 1's are available (for r digits : no. of possible words , w_r=x_r+y_r)

since each 0 provides with two cases next digit can be (0 and 1) and each 1 provides with 1 case (next digit is 0)
so, x_r+1=x_r+y_r=w_r and y_r+1=x_r

for r+1 : total no. words, w_r+1 = x_r+1 + y_r+1

since x_r+1 = w_r and y_r+1 = x_r=w_r-1

so, w_r+1 = w_r+w_r-1

also we know w₁=2, w₂=3.....

the formula which I have shown can be derived by generating polynomials which i learned from Hari sir :)

http://www.goiit.com/posts/list/differential-calculus-hard-question-951552.htm