calculus recurence

Question

You have access to 1×1 tiles which come in 2 different colors and 1×2 tiles which come in 3 different colors. We want to figure out how many different 1×n path designs we can make out of these tiles.

Find a recursive definition of the number of paths of length n

Solve the recurrence relation using the characteristic root technique. 

Answer 1

Assumption 1) all the colors involved are different and the 1x2 tiles have only a single color on each one.

Assumption 2) there are n "boxes" for tiles which can contain either a 1x1 tile or a 1x2 tile.

Assumption 3) the number of each kind of tile available is unlimited.

First from the n available boxes pick j of them to contain 1x1 tiles; these tiles can be arranged in 2^j ways;

there are _nC_j*2^j ways to do this.

In the remaining (n-j) boxes place the larger tiles; there are (n-j)*3^n-j ways to do this.

Now take the product of the ways to arrange the smaller tiles times the number of ways to arrange the larger tiles and sum these products from j=0 to n.