2008 WOOT Sequences [PDF]

Zitiervorschau

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan 1

Arithmetico-Geometric Sequences

An arithmetico-geometric sequence is one which has the form a0 , a1 r, a2 r2 , a3 r3 , . . . , where the sequence {ai } is arithmetic. Sequences like this can be summed using a similar method to the one for geometric series. Problem. What is

5 2n − 1 3 1 ? + 2 + 3 + ··· + 2 2 2 2n

Solution. Let S be the sum. Then we have 2S = 1 +

3 5 2n − 1 + 2 + · · · + n−1 . 2 2 2

Subtracting the original sum, S =1+

2 2 2 2 2n − 1 + + 3 + · · · + n−1 − . 2 22 2 2 2n

Using the usual formula for a geometric series, this is S

2

2n − 1 1 − (1/2)n−1 − 1/2 2n 2n + 3 = 3− . 2n =

1+

Telescoping

We illustrate telescoping with an example. Problem. What is

∞ X

1 ? n(n + 1) n=1 Solution. Call the sum S. To avoid problems with convergence, we use telescoping to compute partial sums rather than the full sum. The pth partial sum Sp is given by

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan

Sp

p X

1 n(n + 1) n=1   p X 1 1 − = n n+1 n=1 ! ! p p+1 X X 1 1 = − n n n=1 n=2 =

=

1−

1 . p+1

By definition, the sum S of the original series is the limit of Sp as p goes to infinity. Clearly this is 1. Pp More generally, if you need to determine 0 f (n), and you can find a function g such that f (n) = g(n) − g(n + 1), you can telescope the sum to get g(0) − g(p + 1). This technique is especially useful with rational functions like the one in the example, because you can decompose a rational function into a sum or difference of other rational functions. Sometimes it also helps with trigonometric sums. Problem. What is

90 X

n sin(2n◦ )?

n=1

Solution. Let S be our sum. Since there’s no obvious way to break the summand into a difference of f (n) and f (n + 1), we try multiplying it by sin(1◦ ), which will allow us to use the product-to-sum formula to create a difference in the summand. We have ◦

S sin(1 )

=

90 X

n sin(1◦ ) sin(2n◦ )

n=1

S sin(1◦ )

=

2S sin(1◦ )

=

90 X 1 n[cos((2n − 1)◦ ) − cos((2n + 1)◦ )] 2 n=1 90 X

n[cos((2n − 1)◦ ) − cos((2n + 1)◦ )]

n=1

Now the only thing stopping us from telescoping is the factor of n in the summand. Rewriting the summation may make it more clear how to proceed:

2S sin(1◦ ) = (cos 1◦ − cos 3◦ ) + 2(cos 3◦ − cos 5◦ ) + · · · + 89(cos 177◦ − cos 179◦ ) + 90(cos 179◦ − cos 181◦ )

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan Using cos(x) = − cos(180◦ − x), we notice that we can group the n = 1 term with the n = 89 term, the n = 2 term with the n = 88 term, and so on, which gives us

2S sin(1◦ )

90[(cos 1◦ − cos 3◦ ) + · · · + (cos 87◦ − cos 89◦ )]

=

+ 45(cos 89◦ − cos 91◦ ) + 90(cos 179◦ − cos 181◦ )

3

2S sin(1◦ )

=

90(cos 1◦ − cos 89◦ ) + 90 cos 89◦

2S sin(1◦ )

=

90 cos 1◦

S

=

45 cot 1◦

Linear Recurrences

A sequence is given by a recurrence if each term is defined in terms of the previous ones. A particularly common type of recurrence is a linear recurrence. A linear recurrence is a sequence x1 , x2 , x3 , · · · in which every term after the kth is given by xn = a1 xn−1 + a2 xn−2 + · · · + ak xn−k . The first k terms must be specified explicitly to define the full sequence. Often we want to “solve” a linear recurrence, which means to find an explicit formula for the terms. The key to doing this is to guess that the answer is yn = λn , where λ is an unknown constant. Our recurrence then becomes λn = a1 λn−1 + a2 λn−2 + · · · + ak λn−k , which simplifies to λk − a1 λk−1 − a2 λk−2 − · · · − ak = 0. This polynomial is known as the characteristic polynomial of the recurrence. If λ is any root of this polynomial, then the sequence yn = λn satisfies the recurrence. In fact, if the roots are distinct values λ1 , λ2 , . . . , λk , the general solution to the recurrence is xn = c1 λn1 + c2 λn2 + · · · + ck λnk . So to solve the original recurrence, given x1 , x2 , . . . , xk , we just need to solve for the proper ci ’s. There is an extension to the formula for the general solution which applies when the characteristic polynomial has repeated roots. If a root λ has multiplicity m, then its contribution to the general solution is (d0 + d1 n + d2 n2 + · · · + dm nm )λn

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan rather than merely cλn . Problem. Solve the recurrence xn+1 = 7xn − 12xn−1 if x0 = 2 and x1 = 7. Solution. The characteristic polynomial here is λ2 − 7λ + 12 = 0, which factors to (λ − 3)(λ − 4) = 0. Thus the general solution is xn = c1 · 3n + c2 · 4n . Clearly xn = 3n + 4n matches the initial conditions x0 = 2 and x1 = 7, so that is the answer. Problem. How many ways are there to tile a 2 × n board using only rectangles of size 2 × 2 and 2 × 1? Solution. Assume the horizontal dimension is n, and let xn be the number of tilings. We can split possible tilings into three cases according to how we tile the left end of the board: • Use a 2 × 2 rectangle. • Place a 2 × 1 rectangle vertically. • Place two 2 × 1 rectangles horizontally. These cases contribute xn−2 , xn−1 , and xn−2 configurations, respectively, to the overall total. Therefore, we have the recurrence xn = xn−1 + 2xn−2 . The characteristic equation is λ2 − λ − 2 = 0, which has solutions 2 and −1, so xn must be of the form c1 (2n ) + c2 (−1)n . We can use some small cases (for example x1 = 1 and x2 = 3) to solve for c1 and c2 , and we end up with xn =

2 n 1 2 + (−1)n . 3 3

Problem. Solve the recurrence a0 = 1, a1 = 6, an+2 = 6an+1 − 9an . Solution. This time the characteristic equation is λ2 − 6λ + 9 = (λ − 3)2 = 0, which has a double root of 3. So the general solution is (d0 + d1 n)(3n ). From the initial conditions, we can solve for d0 and d1 , and we find that d0 = d1 = 1. So an = 3n (n + 1).

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan 4

Inhomogeneous Recurrences

The recurrences of the previous section were homogeneous, meaning that each term in the definition of xn was a multiple of xn−i for some integer i. An inhomogeneous linear recurrence is one which has the form xn = a1 xn−1 + a2 xn−2 + · · · + ak xn−k + f (n) (again for n > k). Suppose that the sequences {yn } and {zn } both satisfy this recurrence. Then by plugging each sequence into the recurrence and subtracting, we can prove that their difference, wn = yn − zn , satisfies the recurrence xn = a1 xn−1 + a2 xn−2 + · · · + ak xn−k , the “homogeneous version” of the original recurrence. This means that if we can find one solution {pn } of the original recurrence, a so-called particular solution, every other solution will have the form xn = pn + c1 λn1 + c2 λn2 + · · · + ck λnk , where the c’s are arbitrary constants and the λ’s are the roots of the characteristic equation (just as in the homogeneous case). The remaining piece of the puzzle is how to find a particular solution. There is a general rule of thumb which applies when f (n) is a polynomial, and that is that the particular solution is also a polynomial. (To be more precise, one of the many possible particular solutions is a polynomial.) You can find the polynomial by guessing its degree (try low numbers first) and then substituting an arbitrary polynomial of that degree into the recurrence, which should let you solve for the coefficients. (Note: the particular solution you find will not in general satisfy the initial conditions; the initial conditions let you solve for the coefficients of the λn terms.) Problem. What is the (2n)th term in the sequence 1, 2, 4, 5, 10, 11, 22, 23, 46, 47, . . . ? This sequence is simple enough that you can probably guess the answer without recurrences. Take a moment to try. Now, suppose you didn’t see it. Can we find the answer systematically? Solution. Let an be the (2n)th term of the original sequence. Then a1 = 2, and we have the recurrence an+1 = 2an + 1. The corresponding homogeneous recurrence is an+1 = 2an ,

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan which has the solutions an = c(2n ). Now we must find a particular solution to the recurrence. It will be a polynomial, so we try the simplest option, a constant. If an = k, we have k = 2k + 1, so k = −1. Thus a particular solution is −1, and the general solution is an = c(2n ) − 1. Since a1 = 2, c = 3/2, and our final answer is an =

3 n (2 ) − 1 = 3(2n−1 ) − 1. 2

Problem. Solve the recurrence a0 = 0, an+1 = 2an + n. Solution. As in the last problem, the solution to the corresponding homogeneous recurrence is would be c(2n ). To find a particular solution, let’s again try setting an = k, where k is a constant. Substituting into the recurrence gives k = 2k + n, which clearly cannot be satisfied for all n. We should therefore try a higher-degree polynomial. Suppose an = bn + d. Then our recurrence becomes b(n + 1) + d = 2(bn + d) + n, or bn + n + d − b = 0. Since this equation must hold for all n, we have b = d = −1, and our particular solution is −n − 1. The general solution is c(2n ) − n − 1, and from a0 = 0 we quickly find that c = 1. So an = 2n − n − 1.

5

Finite differences

Given a sequence that is generated by a polynomial, it’s worth knowing how to extract that polynomial. We will illustrate with an example. Problem. Find the (simplest) polynomial sequence an such that a0 = 4, a1 = 10, a2 = 26, a3 = 58, a4 = 112, a5 = 194. Solution. We write the given entries in a row and then compute the differences of successive terms, writing those values in the next row. We repeat the process until we reach a row of zeros. The resulting table contains the finite differences of the sequence: 4 6 10 6 0

10 16 16 6 0

26 32 22 6 ...

58 112 54 82 28 . . . ...

194 ...

...

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan We read off the first entry in each row to form a new sequence {bn } = 4, 6, 10, 6. It turns out that the formula for the sequence is given by       n n n b0 + b1 + b2 + ··· , 0 1 2 which in our case is

        n n n n 4 +6 + 10 +6 . 0 1 2 3

Expanding out the combinations will lead to the formula an = n3 + 2n2 + 3n + 4. Note that we made an assumption that the fifth row consisted entirely of 0s. If this were not true, the polynomial would have more terms. Since the problem asked for the polynomial of lowest degree that fits the given numbers, we stop at the fifth row. We will not prove that the method given above works, but it is not too hard to do on your own. Notice that every entry in the top row can be expressed as a linear combination of the bi ’s, where the coefficients of the linear combination vary with n but are fixed for all sequences. If you try to work out these coefficients, you will quickly see Pascal’s triangle emerging, which is why the combinations arise.

6

Other problems

Many problems involve sequences and series that don’t fall into any of the usual categories (arithmetic, geometric, arithmeto-geometric, telescoping, recursive), and thus require some creativity. Here is an example. Problem. In a finite sequence of real numbers the sum of any seven successive terms is negative, and the sum of any eleven successive terms is positive. Determine the maximum number of terms in the sequence. (1977 IMO) Solution. The maximum is 16. Suppose the sequence a1 , a2 , . . . , a17 worked. Then we could form the following 7 × 11 table: a1 a2 .. .

a2 a3 .. .

... ... .. .

a11 a12 .. .

a7

a8

...

a17

The columns would have to sum to negative numbers, whereas the rows would have to sum to positive numbers, a contradiction. One can find a sequence of length 16 which works by trial and error, or by assuming that the groups of 11 sum to (say) 1 and the groups of 7 sum to −1, and then solving the resulting system of linear equations. An example of a valid sequence is 5, 5, −13, 5, 5, 5, −13, 5, 5, −13, 5, 5, 5, −13, 5, 5.

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan 7

Exercises 1. Find a closed-form expression for 1(1!) + 2(2!) + 3(3!) + · · · + n(n!). 2. Let a, b be integers. Define a sequence a0 , a1 , . . . of integers by a0 = a, a1 = b, a2 = 2b − a + 2, an+3 = 3an+2 − 3an+1 + an . Determine all pairs (a, b) for which an is a perfect square for all n ≥ 1998. (Vietnam 1998) 3. Solve this recurrence: a0 = 0,

an+1 = 1 +

n−1 X

ai

for n ≥ 0.

i=0

4. How many strings of 1’s and 0’s having length n do not contain two consecutive 0’s? P∞ 1 ? 5. What is n=1 (2n−1)(2n+1) 6. What is

P∞

1 n=1 n(n+1)(n+2) ?

∞ X

7. Evaluate

−1



cot

n=3

n2 2



8. The sequence {an } is defined by a1 = a2 = a3 = 1 and an+1 =

1 + an an−1 . an−2

Find a formula for an . 9. If xn+1 =

xn 1+nxn ,

find an expression for xn in terms of x0 .

10. Let c be a positive integer. The sequence {fn } is defined as follows: f1 = 1,

f2 = c,

fn+1 = 2fn − fn−1 + 2

(n ≥ 2).

Show that for each positive integer k there exists a positive integer r such that fk fk+1 = fr . (1984 IMO shortlist) 11. A sequence {an } is defined by means of the recursion a1 = 1,

an+1 =

√ 1 + 4an + 1 + 24an . 16

Find an explicit formula for an . (1981 IMO shortlist)

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital

Art of Problem Solving

WOOT 2008-09 Sequences & Series Sean Markan 12. Let n1 < n2 < · · · be a sequence of natural numbers such that for i < j, the decimal representation of ni does not occur as the leftmost digits of the decimal representation of nj . (For example, 137 and 13729 cannot both occur in the sequence.) Prove that ∞ X 1 1 1 ≤ 1 + + ··· + . n 2 9 i=1 i

(Iran 1998) 13. Prove that the sequence {an } defined by a1 = 1 and an = an−1 + abn/2c

n = 2, 3, 4, . . .

contains infinitely many integers divisible by 7. (Poland 1998)

Worldwide Online Olympiad Training www.artofproblemsolving.com Sponsored by D. E. Shaw group and Jane Street Capital