Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles. There are three kind of tile.
One is of size 1.
Second is of size 2 of green color.
Third is of size 2 with blue color.
These are the values I found but I can not figure out the formula.
P1 1
p2 3
p3 5
p4 9
p5 21
 A: The recurrence can be expressed as:
$$P(n)=P(n-1)+2*P(n-2)$$
A: Just adding an intuitive way to look at the solution where we do not calculate the no of ways and try to frame formula that fits the numbers (instead we do the other way around and first get a relation then check if it is correct).
$P(n) =$ for length n, how many possible arrangements
We get 3 cases (or three types of different arrangements):-

*

*For this first we place tile of size 1 in corner place and then the rest is $P(n-1)$ as the left out length is n-1.


*For this first we place green tile of size 2 in corner place and then rest is $P(n-2)$ as the left out length is n-2.


*For this we place blue color tile of size 2 in corner and as above we get rest is $P(n-2)$

All the 3 cases are mutually exclusive. So,
$P(n) = P(n-1) + 2 * P(n-2)$
NOTE: There is only one way to place the first tiles in the corner, else we might get higher coefficients for the terms in the formula.

This method uses the divide/decrease and conquer intuition
