SOLUTIONS

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

65^{∗}. [1994, 47] Proposed by Stanley Rabinowitz, Westford, Massachusetts.

Evaluate

∑_{k=0}^{n} |\binom{n}{k} − 2^{k}|.

Comment by the proposer.

I have no solution to this problem. It is equivalent to the question:

“When is 2^{k} > \binom{n}{k} ?”

For a related problem, see problem E3327 in the American Mathematical Monthly, May 1989, pp. 445–446 and the solution to problem E3327 in the American Mathematical Monthly, February 1991, pp. 164–165.

Comment by the editor.

The problem remains open.

66. [1994, 47] Proposed by Alvin Beltramo (student), Central Missouri State University, Warrensburg, Missouri.

Consider the following generalization of the car and the goats problem. A TV host shows you d doors, a car is hidden behind w doors and the rest of the doors are hiding goats. You get to pick a door, winning whatever is behind it. The host, who knows where the cars are, then opens s doors, in the process revealing x cars. The host invites you to switch your choice if you so wish. When should you switch?

Solution by N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin.

The probability that you initially pick a door with a car hidden behind it is w/d. A reasonable strategy for switching would be — switch if the probability of picking a door with a car behind it is greater than w/d.

Let C_{1} and C_{2} denote the events that a car is hidden behind the first and second doors picked, respectively. In order to compute P (C_{2}), consider the probability tree diagram below:

\frac{w}{d}  •^{C_{1}}  _{\frac{w−x−1}{d−s−1}}  •^{C_{2}}

•

\frac{d−w}{d}

•^{\overline{C}_{1}}  _{\frac{w−x}{d−s−1}}  •^{C_{2}}

So

\begin{aligned}P (C_{2}) & = \frac{w}{d} (\frac{w − x − 1}{d − s − 1}) + (\frac{d − w}{d} ) (\frac{w − x}{d − s − 1}) \\ & = \frac{d(w − x) − w}{d(d − s − 1)} . \end{aligned}

When is P (C_{2}) > w/d? Solving yields the following equivalent inequalities:

\begin{aligned}\frac{d(w − x) − w}{d(d − s − 1)} & > \frac{w}{d} , \\ d(w − x) − w & > w(d − s − 1), \\ ws & > dx, \\ \frac{w}{d} & > \frac{x}{s}. \end{aligned}

Hence, P (C_{2}) > w/d if and only if x/s < w/d.

So you should switch and pick a new door if the proportion of cars revealed by the host, x/s, is less than the original proportion of cars, w/d.

Also solved by the proposer.

67. [1994, 47] Proposed by Leonard L. Palmer, Southeast Missouri State University, Cape Girardeau, Missouri.

Show that one more than four times the product of two consecutive even or odd numbered triangular numbers is a square.

Solution by Bob Prielipp, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Larry Hoehn, Austin Peay State University, Clarksville, Tennessee; John Koker, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Joe Howard, New Mexico Highlands University, Las Vegas, New Mexico; Lawrence Somer, Catholic University of America, Washington, D.C.; Joseph E. Chance, University of Texas–Pan American, Edinburg, Texas; Russell Euler, Northwest Missouri State University, Maryville, Missouri; Donald P. Skow, University of Texas–Pan American, Edinburg, Texas; and the proposer.

4T_{n}T_{n+2} + 1 = 4 (\frac{n(n + 1)}{2}) (\frac{(n + 2)(n + 3)}{2}) + 1

= [n(n + 3)][(n + 1)(n + 2)] + 1
= (n^{2} + 3n)[(n^{2} + 3n) + 2] + 1
= (n^{2} + 3n)^{2} + 2(n^{2} + 3n) + 1
= [(n^{2} + 3n) + 1]^{2} = (n^{2} + 3n + 1)^{2}.

Also solved by Herta T. Freitag, Roanoke, Virginia; Melissa Young (student) Hollins College, Roanoke, Virginia; J. Sriskandarajah, University of Wisconsin Center–Richland, Richland Center, Wisconsin; N. J. Kuenzi, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; Tony Reese, University of Wisconsin–Oshkosh, Oshkosh, Wisconsin; and Hushang Poorkarimi, University of Texas–Pan American, Edinburg, Texas.

Comment by the editor. Can anyone generalize this result?

68. [1994, 48] Proposed by Joseph B. Dence, University of Missouri–St. Louis, St. Louis, Missouri.

Let the generalized Fibonacci sequence {U_{n}(P, Q)}_{n=0}^{∞} be defined by the Binet formula

U_{n}(P, Q) = \frac{α^{n} − β^{n}}{α − β} ,

where P, Q ∈ ℤ, P^{2} − 4Q > 0, and α and β are the unequal roots of x^{2} − P x + Q = 0. For a particular case denote U_{n}(2, −1) by P_{n}, the sequence of Pell numbers. Now consider the series of reciprocals:

S = ∑_{k=0}^{∞} P_{2^{k}}^{−1}.

Show that S is irrational by finding its value explicitly.

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

We begin by noting that

P_{n} = \frac{(1 + \sqrt{2})^{n} − (1 − \sqrt{2})^{n}}{2\sqrt{2}}

so P_{1} = 1,P_{2} = 2, P_{3} = 5, P_{4} = 12, P_{5} = 29, P_{6} = 70, P_{7} = 169, P_{8} = 408, . . .. Consider

S(n) = ∑_{j=0}^{n} \frac{1}{P_{2^{j}}} .

S(1) = 3/2 = 2 − 1/2, S(2) = 19/12 = 2 − 5/12, S(3) = 647/408 = 2 − 169/408, . . .. It appears that

(∗)  S(n) = 2 − \frac{P_{2^{n}−1}}{P_{2^{n}}}

for each positive integer n.

We next establish two preliminary results. \underline{Lemma 1}.

\frac{P_{2^{k}−1}}{P_{2^{k}}} = \frac{(1 + \sqrt{2})^{2^{k+1}−1} − (1 − \sqrt{2})^{2^{k+1}−1} + 2\sqrt{2}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}}

where k is an arbitrary positive integer. \underline{Proof}.

\frac{P_{2^{k}−1}}{P_{2^{k}}} = \frac{(1 + \sqrt{2})^{2^{k}−1} − (1 − \sqrt{2})^{2^{k}−1}}{(1 + \sqrt{2})^{2^{k}} − (1 − \sqrt{2})^{2^{k}}}

= \frac{(1 + \sqrt{2})^{2^{k}−1} − (1 − \sqrt{2})^{2^{k}−1}}{(1 + \sqrt{2})^{2^{k}} − (1 − \sqrt{2})^{2^{k}}} · \frac{(1 + \sqrt{2})^{2^{k}} + (1 − \sqrt{2})^{2^{k}}}{(1 + \sqrt{2})^{2^{k}} + (1 − \sqrt{2})^{2^{k}}}

= \frac{(1 + \sqrt{2})^{2^{k+1}−1} − (−1)(1 + \sqrt{2}) + (−1)(1 − \sqrt{2}) − (1 − \sqrt{2})^{2^{k+1}−1}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}}

= \frac{(1 + \sqrt{2})^{2^{k+1}−1} − (1 − \sqrt{2})^{2^{k+1}−1} + 2\sqrt{2}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}}.

\underline{Lemma 2}.

\frac{P_{2^{k}−1}}{P_{2^{k}}} − \frac{1}{P_{2^{k+1}}} = \frac{P_{2^{k+1}−1}}{P_{2^{k+1}}}

where k is an arbitrary positive integer. \underline{Proof}. Using Lemma 1,

\frac{P_{2^{k}−1}}{P_{2^{k}}} − \frac{1}{P_{2^{k+1}}}

= \frac{(1 + \sqrt{2})^{2^{k+1}−1} − (1 − \sqrt{2})^{2^{k+1}−1} + 2\sqrt{2}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}} − \frac{2\sqrt{2}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}}

= \frac{(1 + \sqrt{2})^{2^{k+1}−1} − (1 − \sqrt{2})^{2^{k+1}−1}}{(1 + \sqrt{2})^{2^{k+1}} − (1 − \sqrt{2})^{2^{k+1}}} = \frac{P_{2^{k+1}−1}}{P_{2^{k+1}}} .

We now proceed to prove (∗) using mathematical induction. It is easy to check that the required result holds when n = 1. Assume that

S(k) = 2 − \frac{P_{2^{k}−1}}{P_{2^{k}}}

where k is an arbitrary fixed positive integer. Then, using Lemma 2,

S(k + 1) = ∑_{j=0}^{k+1} \frac{1}{P_{2^{j}}} = S(k) + \frac{1}{P_{2^{k+1}}}

= (2 − \frac{P_{2^{k}−1}}{P_{2^{k}}} ) + \frac{1}{P_{2^{k+1}}} = 2 − (\frac{P_{2^{k}−1}}{P_{2^{k}}} − \frac{1}{P_{2^{k+1}}} )

= 2 − \frac{P_{2^{k+1}−1}}{P_{2^{k+1}}} .

Hence, if the desired result holds when n = k, then it also holds when n = k + 1. (∗) now follows by mathematical induction.

Using the fact that

−1 < \frac{1 − \sqrt{2}}{1 + \sqrt{2}} < 0,

it follows that

S = ∑_{j=0}^{∞} \frac{1}{P_{2^{j}}} = lim_{n→∞} ∑_{j=0}^{n} \frac{1}{P_{2^{j}}}

= lim_{n→∞} S(n) = lim_{n→∞} (2 − \frac{P_{2^{n}−1}}{P_{2^{n}}} )

= 2 − lim_{n→∞} \frac{(1 + \sqrt{2})^{2^{n}−1} − (1 − \sqrt{2})^{2^{n}−1}}{(1 + \sqrt{2})^{2^{n}} − (1 − \sqrt{2})^{2^{n}}}

= 2 − lim_{n→∞} \frac{1 − (\frac{1−\sqrt{2}}{1+\sqrt{2}})^{2^{n}−1}}{(1 + \sqrt{2}) − (\frac{1−\sqrt{2}}{1+\sqrt{2}})^{2^{n}−1} (1 − \sqrt{2})}

= 2 − \frac{1}{1 + \sqrt{2}} = 2 − (\sqrt{2} − 1) = 3 − \sqrt{2}.

Because S = 3 − \sqrt{2}, S is irrational.

Solution II by Gerald E. Bergum, South Dakota State University, Brookings, South Dakota.

In [1, page 225], Lucas derived the formula

(1)  ∑_{n=1}^{∞} \frac{Q^{2^{n−1}r}}{U_{2^{n}r}} = \frac{β^{r}}{U_{r}} , r ≥ 1,

where Q and β are as given in the statement of the problem. Letting P = 2, Q = −1, and r = 1, we have the Pell sequence and (1) becomes

(2)  ∑_{n=1}^{∞} \frac{(−1)^{2^{n−1}}}{P_{2^{n}}} = 1 − \sqrt{2}

since U_{1} = P_{1} = 1. Expanding the left side of (2) and adding the correct terms to get the proper summation we have

S = ∑_{n=0}^{∞} \frac{1}{P_{2^{n}}} = 1 − \sqrt{2} + \frac{1}{2} + \frac{1}{2} + 1 = 3 − \sqrt{2}.

Hence, S is irrational.

\underline{References}

1. E. Lucas, “Théorie des fonctions Numériques Simplement Périodiques,” American Journal of Math., 1 (1878), 184–240.

Also solved by Wayne McDaniel, University of Missouri–St. Louis, St. Louis, Missouri and the proposer. æ