MathDB
INMO 2018 -- Problem #2

Source: INMO 2018

January 21, 2018
number theoryrecursion

Problem Statement

For any natural number nn, consider a 1×n1\times n rectangular board made up of nn unit squares. This is covered by 33 types of tiles : 1×11\times 1 red tile, 1×11\times 1 green tile and 1×21\times 2 domino. (For example, we can have 55 types of tiling when n=2n=2 : red-red ; red-green ; green-red ; green-green ; and blue.) Let tnt_n denote the number of ways of covering 1×n1\times n rectangular board by these 33 types of tiles. Prove that, tnt_n divides t2n+1t_{2n+1}.
Back to ProblemsView on AoPS