Question

A sidewalk with n squares (in one long row) is to be painted. Each square will be painted red, blue, or yellow with the property that adjacent squares are always colored differently. Let on be a sequence counting the number of ways to color a sidewalk of length n. (a) Compute c1, C2, c3, and c4. (b) Find a recursive formula for cn (c) Find a closed formula for cn (d) Use induction to prove that your closed formula is correct.

Answer 1

a) C₁ = 3 as there are 3 ways to colour 1 square.
C₂ = 3*2 = 6 ways as adjascent squares cannot have the same colour
C₃ = 3*2*2 = 12 ways
C₄ = 3*2*2*2 = 24 ways

b) Using the above same logic, the recursive formula here is computed as:

C_n = C_n-1 * (2), n greater or equal to 2. This is because the n^th square can only have 2 colours and cannot have the same colour as the (n-1)^th square.

c) Again from the above recursive formula, we can easily derive the closed formula for C_n as:

3 22-1 7t

This is the required closed formula here.

d) Checking by induction:

For n = 1, C₁ = 3 which is true.

Now assuming that C_k = 3*2^k-1 is true, C_k+1 = 3*2^k-1*2 = 3*2^k which is the formula,

Therefore proved by induction that the closed formula is correct here.