PICTURE httppuushezbw12af70aa634png Consider Tiling a 1Solut

PICTURE: http://puu.sh/ezbw1/2af70aa634.png

Consider Tiling a 1

Solution

F : 1 1 2 3 5 8 13 ... ...

a) Base case P(1) =F₂  = 1 as only one combination is possible i.e {1}

P(2) = F₃ = 2 as there can be 2 combinations : {1,1} and {2}.

b) Now assuming P(n) and P(n+1) are true i.e number of ways of arranging tiles in 1Xn and 1 X n+1 strips .

So for P(n+2) we can select the first tile to be single length tile .

So possible number of such configurations are P(n+1).

or selecting the first tile to be tile of length 2, possible number of configurations are P(n).

So total number of configurations are P(n+2) = P(n+1) +P(n).

So, if P(n) and P(n+1) are (n+1)th and (n+2)th fibonacci numbers, then P(n+2) is the (n+3)rd fibonacci number. (Proved).

So T(n) = F_n+1