Question

Suppose there is a toy which takes either 'a' or 'b' as input. Total number of inputs=n. If two consecutive inputs are 'a' the toy crashes. What is the total number of ways in which the toy does NOT crash?

Answer 1

Looks like an offsetted fibbonacci sequence.

f(1) = 2 ; a b
f(2) = 3 ; ab ba bb
f(3) = 5 ; abb aba bab bbb bba
f(4) = 8 ; abbb abba abab babb baba bbba bbbb bbab
f(5) = 13 etc.

In general:

f(1) = 2 , f(2) = 3, f(n) = f(n-1) + f(n-2) ; n>=3

See
http://www.mathsisfun.com/numbers/fibonacci-sequence.html

Answer 2

So basically you're saying that f(n) for some n is the some of the first n fibonacci numbers?

Answer 3

rather it is the nth term of the fibonacci sequence?

Answer 4

Ok thanks a lot sir/ma'm....

Answer 5

m=1 ; total ways not to crash toy is fib(4) = 2
m=2 ; total ways not to crash toy is fib(5) = 3
:
:
m=n ; total ways not to crash toy is fib(n+3)

So, for n inputs, the total number of ways not to crash the toy is the (n+3)'th term of the fibonacci sequence

Answer 6

Actually - in the fibonacci series, terms are counted from 0:

fib(0)=0 , fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8, fib(7)=13, ...

So, for n inputs, the total number of ways not to crash the toy is the (n+2)'th term of the fibonacci sequence (0,1,1,2,3,5,8,13,...) counting the terms from 0.

Then you can also use this formula to calculate the answer for any n:
\[fib(n)=\frac{\phi^{n}-(1-\phi)^{n}}{\sqrt{5}}\]

where phi is the golden ratio , approximately:
\[\phi=\frac{1+\sqrt{5}}{2}\]

See:
http://www.mathsisfun.com/numbers/fibonacci-sequence.html
http://www.mathsisfun.com/numbers/golden-ratio.html