SOLUTIONS

No problem is ever permanently closed. Any comments, new solutions, or new insights on old problems are always welcomed by the problem editor.

49. [1992, 145] Proposed by Mohammad K. Azarian, University of Evansville, Evansville, Indiana.

Let

A = ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{m} sin(\frac{iπ}{3} ) cos(\frac{jπ}{3} ) csc(\frac{2^{k}π}{3} ).

Show that

A ≤ \frac{4\sqrt{3}}{3} if m is odd and A = 0 if m is even.

Solution I by Bob Prielipp, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin.

Our solution will use the following known results.

(1)  ∑_{k=1}^{n} cos kx = sin \frac{nx}{2} cos(n + 1)\frac{x}{2}/ sin \frac{x}{2}

(2)  ∑_{k=1}^{n} sin kx = sin \frac{nx}{2} sin(n + 1)\frac{x}{2}/ sin \frac{x}{2}

for every x that is not a multiple of 2π. (For a proof of these results, see p. 366 of Apostol; Mathematical Analysis: A Modern Approach to Advanced Calculus; Addison-Wesley Publishing Company, Inc.; Reading Massachusetts; 1957.)

A = ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{m} sin(\frac{iπ}{3} ) cos(\frac{jπ}{3} ) csc(\frac{2^{k}π}{3} )

= ∑_{i=1}^{n} sin(\frac{iπ}{3} ) ∑_{j=1}^{n} cos(\frac{jπ}{3} ) ∑_{k=1}^{m} csc(\frac{2^{k}π}{3} ).

If m is even,

∑_{k=1}^{m} csc(\frac{2^{k}π}{3} ) = 0

so A = 0. If m is odd,

∑_{k=1}^{m} csc(\frac{2^{k}π}{3} ) = csc(\frac{2π}{3} ) = \frac{2\sqrt{3}}{3}.

Thus,

A = \frac{2\sqrt{3}}{3} ∑_{i=1}^{n} sin(\frac{iπ}{3} ) ∑_{j=1}^{n} cos(\frac{jπ}{3} )

= \frac{2\sqrt{3}}{3} \frac{sin \frac{nπ}{6} sin \frac{(n+1)π}{6}}{sin(\frac{π}{6} )} sin \frac{nπ}{6} cos \frac{(n+1)π}{6} ; sin (\frac{π}{6} )

= \frac{4\sqrt{3}}{3} sin \frac{nπ}{6} sin \frac{nπ}{6} sin \frac{(n + 1)π}{3}

≤ \frac{4\sqrt{3}}{3} · 1 · 1 · 1 = \frac{4\sqrt{3}}{3}.

Solution II by the proposer.

It is known [1] that for any real number x

(1 − cos x)| ∑_{i=1}^{n} cos ix|| ∑_{i=1}^{n} sin ix| ≤ 1.

Thus, for x = \frac{π}{3} we get

(1)  ∑_{i=1}^{n} ∑_{j=1}^{n} sin(\frac{iπ}{3} ) cos(\frac{jπ}{3} ) ≤ | ∑_{i=1}^{n} sin(\frac{iπ}{3} )|| ∑_{j=1}^{n} cos(\frac{jπ}{3} )| ≤ 2.

Also, since

cot(2^{k−1}x) − cot(2^{k}x) = csc(2^{k}x),

we have

∑_{k=1}^{m} csc(2^{k}x) = cot x − cot(2^{m}x),

and for x = \frac{π}{3} we obtain

(2)  ∑_{k=1}^{m} csc(\frac{2^{k}π}{3} ) = cot \frac{π}{3} − cot(\frac{2^{m}π}{3} ) = \{ \begin{matrix}0, & if m is even; \\ \frac{2\sqrt{3}}{3}, & if m is odd. \end{matrix}

Finally, from (1) and (2) we achieve the desired result.

\underline{References}

1. Problem # 379, College Mathematics Journal, M. K. Azarian (proposer) and Harry D’Souza (solver), 21 (1990), 248.

50. [1992, 145] Proposed by Curtis Cooper and Robert E. Kennedy, Central Missouri State University, Warrensburg, Missouri.

How many ways can a 3 × 1992 floor be tiled with 1 × 2 indistinguishable tiles?

Solution by Lamarr Widmer, Messiah College, Grantham, Pennsylvania and N. J. Kuenzi, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin.

We will let a_{n} denote the number of ways a 3 × 2n floor can be tiled with dominoes (1 × 2 tiles). So our problem is to determine a_{996}.

We can easily check that a_{1} = 3.

Now a tiling of a 3 × 2n rectangle can be separated into two tilings of smaller 3 × 2i and 3 × 2j rectangles like this:

where 2i + 2j = 2n, unless it has a row of horizontal dominoes through its center like this:

To see why this is true, note that if there is no such subdivision, then each of the vertical lines where this would be possible must have a domino lying across it. But since there are an even number of 1 × 1 squares on either side of such a vertical dividing line, it must actually have two dominoes lying across it. It is easy to see what goes wrong if we try to have these two dominoes in the top and bottom rows. Hence, one of them must be in the middle row. It is easy to check that there are exactly two possible tilings which have this horizontal row of dominoes through their center.

We first wish to deduce a general recursive formula for a_{n}. We will illustrate the general recursive principle by means of two examples. We see that there are 9 ways to tile a 3 × 4 floor by putting two tilings of the 3 × 2 floor side by side plus two ways to tile it with the row of horizontal dominoes through the center.

Hence a_{2} = 11.

A similar line of reasoning can be used to compute a_{5}. The following diagram relates a_{5} to its preceding terms.

Therefore,

a_{5} = 3a_{4} + 2a_{3} + 2a_{2} + 2a_{1} + 2.

In general, we have that

a_{n} = 3a_{n−1} + 2a_{n−2} + 2a_{n−3} + 2a_{n−4} + 2a_{n−5} + ⋯ + 2a_{1} + 2.

From this relation we easily derive

a_{n} = 4a_{n−1} − a_{n−2}.

Using the method explained in most discrete mathematics texts, this second order linear recurrence relation yields the explicit formula

a_{n} = (\frac{1}{2} + \frac{\sqrt{3}}{6})(2 + \sqrt{3})^{n} + (\frac{1}{2} − \frac{\sqrt{3}}{6})(2 − \sqrt{3})^{n}.

So we have

a_{996} = (\frac{1}{2} + \frac{\sqrt{3}}{6})(2 + \sqrt{3})^{996} + (\frac{1}{2} − \frac{\sqrt{3}}{6})(2 − \sqrt{3})^{996} ≐ 3.603 · 10^{569}.

Also solved by Stanley Rabinowitz, Westford, Massachusetts and the proposers. Rabinowitz and Kuenzi noted that

a_{n} = ⌈(\frac{1}{2} + \frac{\sqrt{3}}{6})(2 + \sqrt{3})^{n}⌉

for n ≥ 1. In addition, Rabinowitz counted and found that the number of ways to tile a 3 × 1992 floor with 1 × 2 indistinguishable tiles is

3602927240267776227266301236128046740727140862109428584846 6187989288272765115658745939578174574051042816802245305844 6362912165834628327000163077343071409300022653365714290771 3843129066863598893786810870199167529198469052917243505662 2862052760951873433815826479063106067394965812084240925088 9591061988939195168722611435717987995627725683246896965503 4010414559073855237148010444891336978160899220084149304617 3795108177928277627669779323982081706670963802388825487599 4813205199045365601920341350977195999536039979037705807509 971867586054886929272135211907110350307848485081.

Rabinowitz also noted that the problem can be found in a couple of different places. One is a book by W. G. Kelley and A. C. Peterson entitled Difference Equations: An Introduction with Applications. This book is published by Academic Press, Inc. and the problem can be found on pages 89–91. The other place is Problem E2417 in the American Mathematical Monthly. The problem was proposed by Ioan Tomescu and a solution by D. Ž. Djoković was published in volume 81 (1974), pp. 522–523.

51. [1992, 145] Proposed by Alvin Beltramo (student), Central Missouri State University, Warrensburg, Missouri.

A standard deck of 52 cards is shuffled and two different denominations, e.g., king and five, are chosen. What is the probability that two cards, one from each denomination, are consecutive in the deck?

Solution by the proposer.

Label one of the denominations 1 and the other 2. Label the other cards in the deck 0. Now any arrangement of the deck will have a corresponding sequence of 44 0’s, 4 1’s, and 4 2’s associated with it. Moreover, each sequence of 44 0’s, 4 1’s, and 4 2’s will be the unique sequence associated with 44! · 4! · 4! different arrangements of the deck. We will proceed to count the number of different sequences of 44 0’s, 4 1’s, and 4 2’s which do \underline{not} have a 1 and 2 adjacent. If x denotes this number, then x · 44! · 4! · 4! arrangements of the deck do not have 2 cards, one from each denomination, side by side. Thus the probability that 2 cards, one from each denomination, are consecutive in the deck is

1 − \frac{x · 44! · 4! · 4!}{52!}.

To compute x, the number of arrangements of 44 0’s, 4 1’s, and 4 2’s which do not have a 1 and 2 adjacent, let us start by examing all

\binom{8}{4} = 70

arrangements of 4 1’s and 4 2’s. This list of 70 subdivides into 7 groups we will call groups 12, 121, 1212, 12121, 121212, 1212121, and 12121212. In the 12 group we have 2 sequences; they are

11112222 and 22221111.

In the 121 group we have 6 sequences; they are

11122221 11222211 12222111 22211112 22111122 21111222.

The 1212 group has 18 sequences

11122212 22211121 11122122 22211211 11121222 22212111 11222112 22111221 11221122 22112211 11211222 22122111 12221112 21112221 12211122 21122211 12111222 21222111.

Continuing in this manner the 12121 group has 18 elements, the 121212 group has 18 elements, the 1212121 group has 6 elements, and the 12121212 group has 2 elements. For each element in each group we must determine the number of ways we can distribute 44 0’s so that the sequences of 44 0’s, 4 1’s, and 4 2’s do not have 1 and 2 adjacent.

It turns out that if we determine the number of ways to distribute the 44 0’s (so as to not have a 1 and 2 adjacent) in one representative from each of the seven groups, the other group’s members have the same number of ways to distribute the 44 0’s so that 1 and 2 are not adjacent.

Consider 11112222 from the 12 group. Placing 44 0’s in this sequence so that it does not have a 1 and 2 adjacent would involve placing 43 0’s in the 9 boxes, , depicted below.

1  1  1  1 \underbrace{0} 2  2  2  2

Note that at least one 0 must go in the middle box. But by [1], the number of ways to put 43 0’s in 9 boxes is

\binom{9 − 1 + 43}{9 − 1} = \binom{51}{8}.

By a similar discussion there are

\binom{51}{8}

ways to place 44 0’s in 22221111 so that 1 and 2 are not adjacent. Thus, the number of sequences we get from the 12 group is

2 · \binom{51}{8}.

Next take 11122221 from the 121 group. Placing 44 0’s in this sequence so that it does not have a 1 and 2 adjacent would involve placing 42 0’s in the 9 boxes depicted below.

1  1  1 \underbrace{0} 2  2  2  2 \underbrace{0} 1

But the number of ways to do this is

\binom{50}{8}

so the number of sequences we get from the 121 group is

6 · \binom{50}{8}.

Continuing in this manner we have the following chart.

Group  Representative  # in Group  # per Repres.
12  11112222  2  \binom{51}{8}
121  11122221  6  \binom{50}{8}
1212  11122212  18  \binom{49}{8}
12121  11222121  18  \binom{48}{8}
121212  11221212  18  \binom{47}{8}
1212121  12212121  6  \binom{46}{8}
12121212  12121212  2  \binom{45}{8}

Thus,

\begin{matrix}x = & 2\binom{51}{8} + 6\binom{50}{8} + 18\binom{49}{8} + 18\binom{48}{8} \\ + 18\binom{47}{8} + 6\binom{46}{8} + 2\binom{45}{8}. \end{matrix}

Using the computer algebra system DERIVE,

x = 27061623270.

Putting this in

1 − \frac{x · 44! · 4! · 4!}{52!}

and again simplifying using DERIVE, the required probability is

\frac{284622747}{585307450} ≐ 0.486279.

\underline{References}

1. J. L. Mott, A. Kandel, and T. P. Baker, Discrete Mathematics for Computer Scientists, Reston Publishing Company, Reston, VA, (1983), 140–146.

52. [1992, 146] Proposed by Dale Woods and Jin Chen, University of Central Oklahoma, Edmond, Oklahoma.

(a) Find a closed form for the expression

∑_{k=1}^{m} k\binom{2m}{m − k}.

(b)∗ Let n ≥ 2 be an integer. Find a closed form for the expression

∑_{k=1}^{m} k^{n}\binom{2m}{m − k}.

Solution I to (a) by N. J. Kuenzi, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin.

Let

a_{m} = ∑_{k=1}^{m} k\binom{2m}{m − k}.

We will show that

a_{m} = m\binom{2m − 1}{m}

by showing that a_{m} satisfies the recurrence relation

a_{m+1} = 4a_{m} + \binom{2m}{m}

for m ≥ 1 and that the solution to this recurrence relation with initial condition a_{1} = 1 is

a_{m} = m\binom{2m − 1}{m}.

To see the second claim first, let a_{m} be a sequence satisfying the recurrence relation

a_{m+1} = 4a_{m} + \binom{2m}{m}

for m ≥ 1 with a_{1} = 1. Then

a_{1} = 1 = 1\binom{2 − 1}{1}.

Suppose that

a_{n} = n\binom{2n − 1}{n}.

Then

a_{n+1} = 4a_{n} + \binom{2n}{n} = 4n\binom{2n − 1}{n} + \binom{2n}{n}

= \frac{4n(2n − 1)!}{n!(n − 1)!} + \frac{(2n)!}{n!n!}

= \frac{(2n)(2n)!}{n!n!} + \frac{(2n)!}{n!n!}

= \frac{(2n + 1)!}{n!n!} = (n + 1)\binom{2n + 1}{n + 1}.

So by the principle of mathematical induction,

a_{m} = m\binom{2m − 1}{m}

for all positive integers m. Finally, to show that the sequence

a_{m} = ∑_{k=1}^{m} k\binom{2m}{m − k}

satisfies the recurrence relation, we will use the following identity

\binom{n + 2}{j} = \binom{n}{j} + 2\binom{n}{j − 1} + \binom{n}{j − 2}.

Then

a_{m+1} = ∑_{k=1}^{m+1} k\binom{2m + 2}{m + 1 − k}

= ∑_{k=1}^{m−1} k[\binom{2m}{m + 1 − k} + 2\binom{2m}{m − k} + \binom{2m}{m − k − 1}] + m(2m + 2) + (m + 1)

= 2 ∑_{k=1}^{m} k\binom{2m}{m − k} + ∑_{k=1}^{m−1} k\binom{2m}{m + 1 − k} + ∑_{k=1}^{m−1} k\binom{2m}{m − k − 1} + 2m^{2} + m + 1

= 2a_{m} + \binom{2m}{m} + ∑_{k=2}^{m−1} k\binom{2m}{m + 1 − k} + ∑_{k=1}^{m−1} k\binom{2m}{m − k − 1} + 2m^{2} + m + 1

= 2a_{m} + \binom{2m}{m} + ∑_{j=1}^{m−2}(j + 1)\binom{2m}{m − j} + ∑_{i=2}^{m}(i − 1)\binom{2m}{m − i} + 2m^{2} + m + 1

= 2a_{m} + \binom{2m}{m} + ∑_{j=1}^{m−2} j\binom{2m}{m − j} + ∑_{i=2}^{m} i\binom{2m}{m − i} + \binom{2m}{m − 1} + 2m^{2} − m

= 2a_{m} + \binom{2m}{m} + ∑_{j=1}^{m} j\binom{2m}{m − j} + ∑_{i=1}^{m} i\binom{2m}{m − i}

= 4a_{m} + \binom{2m}{m}.

Solution II to (a) by the proposers.

To prove the (a) part we need the fact that for 1 ≤ k ≤ m,

(1)  (m − k)\binom{2m}{m − k} = 2m · \binom{2m − 1}{m − 1 − k}.

This can be shown by using the factorial form of the binomial coefficients. Next, writing (1) in a slightly different form, we have that

(2)  k\binom{2m}{m − k} = m\binom{2m}{m − k} − 2m\binom{2m − 1}{m − 1 − k}.

Now summing both sides of (2) as k ranges between 1 and m and using the assumption that

\binom{2m − 1}{−1} = 0,

we have that

∑_{k=1}^{m} k\binom{2m}{m − k} = ∑_{k=1}^{m}(m\binom{2m}{m − k} − 2m\binom{2m − 1}{m − 1 − k})

= m ∑_{k=1}^{m} \binom{2m}{m − k} − 2m ∑_{k=1}^{m} \binom{2m − 1}{m − 1 − k}

= m ∑_{k=0}^{m−1} \binom{2m}{k} − 2m ∑_{k=0}^{m−2} \binom{2m − 1}{k}

= m\frac{2^{2m} − \binom{2m}{m}}{2} − 2m(2^{2m−2} − \binom{2m − 1}{m − 1})

= m · 2^{2m−1} − \frac{m}{2}\binom{2m}{m} − m · 2^{2m−1} + m · 2\binom{2m − 1}{m − 1}

= \frac{m}{2}\binom{2m}{m}.

Solution III to (a) by the proposers. We need to use the summation by parts formula

∑_{k=1}^{m} b_{k}(a_{k+1} − a_{k}) + ∑_{k=1}^{m} a_{k}(b_{k} − b_{k−1}) = a_{m+1}b_{m} − a_{1}b_{0}.

(This identity can be proved by expanding the summation.) Let b_{k} = k and

a_{k} = ∑_{j=1}^{k−1} \binom{2m}{m − j}.

(Note that a_{1} = 0.) Then using summation by parts

∑_{k=1}^{m} k\binom{2m}{m − k} + ∑_{k=1}^{m} ∑_{j=1}^{k−1} \binom{2m}{m − j} = m ∑_{j=1}^{m} \binom{2m}{m − j}.

Thus

∑_{k=1}^{m} k\binom{2m}{m − k} + ∑_{k=1}^{m−1} k\binom{2m}{k} = m ∑_{k=0}^{m−1} \binom{2m}{k}.

But

k\binom{2m}{k} = 2m\binom{2m − 1}{k − 1}

so we have

∑_{k=1}^{m} k\binom{2m}{m − k} + 2m ∑_{k=1}^{m−1} \binom{2m − 1}{k − 1} = m ∑_{k=0}^{m−1} \binom{2m}{k}.

Therefore,

∑_{k−1}^{m} k\binom{2m}{m − k} = m ∑_{k=0}^{m−1} \binom{2m}{k} − 2m ∑_{k=1}^{m−1} \binom{2m − 1}{k − 1}

= m ∑_{k=0}^{m−1} \binom{2m}{k} − 2m ∑_{k=0}^{m−2} \binom{2m − 1}{k}

= m · \frac{2^{2m} − \binom{2m}{m}}{2} − 2m(\frac{2^{2m−1}}{2} − \binom{2m − 1}{m − 1})

= m · 2^{2m−1} − \frac{m}{2}\binom{2m}{m} − m · 2^{2m−1} + 2m\binom{2m − 1}{m − 1}

= −\frac{m}{2}\binom{2m}{m} + m\binom{2m}{m}

= \frac{m}{2}\binom{2m}{m}.

Part (b) of Problem 52 still remains open.