A 1 n rectangle (n 1) is divided into n unit (1 1) squares. Each square of this rectangle is coloured red, blue or green. Let f(n) be the number of colourings of the rectangle in which there are an even number of red squares. What is the largest prime factor of f(9) / f(3) ? (The number of red squares can be zero)

Step-by-step solution

f(n)= ^n C₀ 2^n+ ^n C₂ 2^ n-2 + ^n C₄ 2^ n-4 + . Now (2+1)^ n = ^ n C ₀ 2^ n + ^ n C ₁ 2^ n -1 + ^ n C ₂ 2^ n -2 + ^ n C ₃ 2^ n -3 + ...(i) (2-1)^n= ^n C₀ 2^n- ^n C₁ 2^ n-1 + ^n C₂ 2^ n-2 - ^n C₃ 2^ n-3 +....(ii) add (1) and (2) 3^n+1=2 [ ^n C₀ 2^n+ ^n C₂ 2^ n-2 + ^n C₄ 2^ n-4 + ]f(n)= 3^n+1 2 f(9)= 3^9+1 2 , f(3)= 3^3+1 2 f(9) f(3) = 3^9+1 3^3+1 =3^6-3^3+1=703=19 37 Largest prime factor is 37 .