Advanced book on Mathematics Olympiad

102 3 Real Analysis

xn=

∑t

i= 1

∑mi

j= 0

βijnjλni−j, forn≥ 0.

As is the case with differential equations, to find the general term of an inhomogeneous
linear recurrence

xn=a 1 xn− 1 +a 2 xn− 2 +···+akxn−k+f (n), n≥ 1 ,

one has to find a particular solution to the recurrence, then add to it the general term of
the associated homogeneous recurrence relation.
Putting these ideas together, let us compute the general-term formula of the Fibonacci
sequence. The recurrence relationFn+ 1 =Fn+Fn− 1 has characteristic equationλ^2 −
λ− 1 =0, with rootsλ 1 , 2 =^1 ±

√

5

2. WritingFn=α^1 λ

n

1 +α^2 λ

n

2 and solving the system

α 1 +α 2 =F 0 = 0 ,

α 1 λ 1 +α 2 λ 2 =F 1 = 1 ,

we obtainα 1 =−α 2 =−√^15. We rediscover the well-known Binet formula

Fn=

1

√

5

((

1 +

√

5

2

)n

−

(

1 −

√

5

2

)n)

.

In the same vein, let us solve a problem published in theAmerican Mathematical
Monthlyby I. Tomescu.

Example.In how many ways can one tile a 2n×3 rectangle with 2×1 tiles?

Solution.Denote byunthe number of such tilings. Start tiling the rectangle from the
short side of length 3, as shown in Figure 17.

Figure 17

In the last two cases from the figure, an uncovered 1×1 square can be covered in a
single way: by the shaded rectangle. We thus obtain

un+ 1 = 3 un+ 2 vn,

wherevnis the number of tilings of a( 2 n− 1 )×3 rectangle with a 1×1 square missing
in one corner, like the one in Figure 18. That figure shows how to continue tiling this
kind of rectangle, giving rise to the recurrence