You are given a 2-by-n grid that you must tile, using either 1-by-2 dominoes or 2-by-2 squares. The dominoes can be arranged either vertically or horizontally. (See Figure 5.27.) Prove by strong...

You are given a 2-by-n grid that you must tile, using either 1-by-2 dominoes or 2-by-2 squares. The dominoes can be arranged either vertically or horizontally. (See Figure 5.27.) Prove by strong induction on n that the number of different ways of tiling the 2-by-n grid is precisely Jn+1. (Be careful: it’s easy to accidentally count some configurations twice—for example, make sure that you count only once the tiling of a 2-by-3 grid that uses three horizontal dominoes.)