0

we have to build a houses on $m$ plots, such that no two consecutive plots exist on which it is allowed to build house calculate the number of possible ways of assigning free plots to buildings

example if we have $3$ plots then no of possible ways mark $X$ as a plot where building is allowed and $Y$ as a free plot, we have: $XYX$, $YXY$, $YYX$, $XYY$, $YYY$.

N. F. Taussig
  • 76,571
sudhanshu
  • 1
  • Welcome to MathSE. It generally considered polite to use proper grammar in your posts (capitalize the beginning of sentences, spell things correctly, use sentences, etc). Please edit your post accordingly. – Mike Pierce Feb 24 '15 at 19:01

1 Answers1

1

If you let X(n) be the number of ways of length n that have an "X" in the first position, and Y(n) the number of ways of length N that have a "Y" in the first position, then you should be able to convince yourself that X(1) = Y(1) = 1, that X(n+1) = Y(n) and Y(n+1) = X(n) + Y(n)

Then by doing some small examples, and/or using the first equation to replace "X(n)" by "Y(n-1)" in the second, you will see that X(n) is the nth Fibonacci number, that Y(n) is the n+1st Fibonacci number, and that the total number of ways of length n = X(n) + Y(n) = the n+2nd Fibonacci number. (Assuming you index the Fibonacci numbers so that the 1st and 2nd are both 1).

Carl Eichenlaub
  • 11