Binary words.

Anant sir.... in the example given 011 is also invalid

number of valid binary words is coming to be (n+2)th term of fibonacci series

Yes Bipin, corrected that.. any proof?

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.

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