SOLUTIONS

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

129. [1999, 196] Proposed by Kenneth B. Davenport, 301 Morea Road, Box 491, Frackville, Pennsylvania.

Let k ≥ 0 and i ≥ 1 be integers. Prove that

∑_{j} \left⟨{k \atop j}\right⟩\binom{k + i − j}{k + 1} = ∑_{m=1}^{i} m^{k},

where

\left⟨{k \atop j}\right⟩

denotes an Eulerian number.

Solution by the proposer and Carl Libis, Antioch College, Yellow Springs, Ohio. Here, an Eulerian number

\left⟨{k \atop j}\right⟩

is the number of permutations π_{1}π_{2} ⋯ π_{k} of {1, 2, …, k} that have j ascents, namely, j places where π_{i} < π_{i+1}. To prove this result we need Worpitsky’s identity from R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, Massachusetts, 1994, p. 269, i.e.

m^{k} = ∑_{j} \left⟨{k \atop j}\right⟩\binom{m + j}{k}

for integer k ≥ 0. Using this identity, rearranging terms, changing index variables, and using properties of Eulerian numbers, we have

∑_{m=1}^{i} m^{k} = ∑_{m=1}^{i} ∑_{j} \left⟨{k \atop j}\right⟩\binom{m + j}{k} = ∑_{j} \left⟨{k \atop j}\right⟩ ∑_{m=1}^{i} \binom{m + j}{k}

= ∑_{j} \left⟨{k \atop j}\right⟩ ∑_{m=j+1}^{i+j} \binom{m}{k} = ∑_{j} \left⟨{k \atop j}\right⟩ ∑_{m=0}^{i+j} \binom{m}{k}

= ∑_{j} \left⟨{k \atop j}\right⟩\binom{i + j + 1}{k + 1} = ∑_{j} \left⟨{k \atop k − 1 − j}\right⟩\binom{i + j + 1}{k + 1}

= ∑_{j} \left⟨{k \atop j}\right⟩\binom{k + i − j}{k + 1}.

130. [1999, 196] Proposed by Joseph Wiener and William Heller, University of Texas–Pan American, Edinburg, Texas.

Show that for any b > 1, the function

f(x) = (x^{2} + (1 − b))e^{x} + bx

has exactly one zero for x ≥ 0.

Solution I by Chris Farmer (student), Northwest Missouri State University, Maryville, Missouri. f(x) is continuous and differentiable throughout its domain. Furthermore,

\begin{matrix}f(0) = [0^{2} + (1 − b)]e^{0} + b(0) = 1 − b \\ f(\sqrt{b − 1}) = [(\sqrt{b − 1})^{2} + (1 − b)]e^{\sqrt{b−1}} + b\sqrt{b − 1} = b\sqrt{b − 1}. \end{matrix}

Since b > 1, f(0) = 1 − b < 0 and f(\sqrt{b − 1}) = b\sqrt{b − 1} > 0. Therefore, by the Intermediate Value Theorem, there exists a c such that 0 < c < \sqrt{b − 1} and f(c) = 0.

Consider f(c) and f(c + a), where a > 0.

f(c) = [c^{2} + (1 − b)]e^{c} + bc = 0.

f(c + a) = [(c + a)^{2} + (1 − b)]e^{c+a} + b(c + a)
= [c^{2} + 2ac + a^{2} + (1 − b)]e^{c+a} + bc + ba
> [c^{2} + (1 − b) + 2ac + a^{2}]e^{c} + bc + ba
= [c^{2} + (1 − b)]e^{c} + bc + (a^{2} + 2ac)e^{c} + ba
= f(c) + (a^{2} + 2ac)e^{c} + ba
= (a^{2} + 2ac)e^{c} + ba.

Since a, b, c > 0, f(c + a) > 0. Therefore, f(x) has no zeros greater than c. Suppose f(x) has another zero d. Then d ≤ c. Repeating the above argument,

with d in place of c, we find that f(x) has no zeros greater than d, so c ≤ d. It follows that c = d.

Therefore, f(x) has exactly one zero.

Also solved by N. J. Kuenzi, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin; Kandasamy Muthuvel, University of Wisconsin-Oshkosh, Oshkosh, Wisconsin; and the proposers.

131. [1999, 197] Proposed by Kenneth B. Davenport, 301 Morea Road, Box 491, Frackville, Pennsylvania.

Show that if

\begin{matrix}A = ∑_{n=0}^{∞}(\frac{1}{9n + 1} − \frac{1}{9n + 4}), B = ∑_{n=0}^{∞}(\frac{1}{9n + 5} − \frac{1}{9n + 8}), \\ C = ∑_{n=0}^{∞}(\frac{1}{9n + 2} − \frac{1}{9n + 5}), D = ∑_{n=0}^{∞}(\frac{1}{9n + 4} − \frac{1}{9n + 7}), \end{matrix}

then A + B = (C + D)α, where α = 2 cos(π/9).

Solution by the proposer. Begin by noting that

A + B = ∫_{0}^{1} \frac{1 + x^{4}}{1 + x^{3} + x^{6}} dx

and

C + D = ∫_{0}^{1} \frac{x + x^{3}}{1 + x^{3} + x^{6}} dx.  (1)

Using the Tables of Indefinite Integrals by G. Petit Bois, Dover Publications, Inc., New York, 1961, p. 105, we have the formula

∫ \frac{x^{m}}{a + bx^{n} + cx^{2n}} dx = \frac{1}{ncq^{2n−m−1} sin ϵ}·

∑_{k=0}^{n−1} [ − sin(n − m − 1)ϵ_{k} · \frac{1}{2} · ln(x^{2} − 2qx cos ϵ_{k} + q^{2})

+ cos(n − m − 1)ϵ_{k} tan^{−1} [\frac{x sin ϵ_{k}}{q − x cos ϵ_{k}} ]],  (2)

where

q = (\frac{a}{c})^{\frac{1}{2n}} , cos ϵ = \frac{−b}{2\sqrt{ac}}, ϵ_{k} = \frac{2kπ + ϵ}{n},

and

b^{2} − 4ac < 0, m < 2n.

Since a = b = c = 1, and n = 3, (2) may be simplified and noting ϵ = 2π/3,

\frac{2\sqrt{3}}{9} ∑_{k=0}^{2} [ − sin(2 − m)ϵ_{k} · \frac{1}{2} ln(2 − 2 cos ϵ_{k}) + cos(2 − m)ϵ_{k} tan^{−1} [\frac{sin ϵ_{k}}{1 − cos ϵ_{k}} ]]

and we must have

ϵ_{0} = \frac{2π}{9} , ϵ_{1} = \frac{8π}{9} , and ϵ_{2} = \frac{14π}{9} .  (3)

Taking the A sum with m = 0 we have

A = \frac{2\sqrt{3}}{9} ∑_{k=0}^{2} [ − sin(2ϵ_{k}) · \frac{1}{2} ln(2 − 2 cos ϵ_{k}) + cos(2ϵ_{k}) tan^{−1} [\frac{sin ϵ_{k}}{1 − cos ϵ_{k}} ]] (4)

= \frac{2\sqrt{3}}{9}[ − sin \frac{4π}{9} · \frac{1}{2} · ln(2 − 2 cos \frac{2π}{9} ) − sin \frac{16π}{9} · \frac{1}{2} ln(2 − 2 cos \frac{8π}{9} )

− sin \frac{28π}{9} · \frac{1}{2} ln(2 − 2 cos \frac{14π}{9} ) + cos \frac{4π}{9} · \frac{7π}{18} + cos \frac{8 · 2π}{9} · \frac{π}{18} − cos \frac{28π}{9} · \frac{5π}{18} ]

B = \frac{2\sqrt{3}}{9} ∑_{k=0}^{2} [ − sin(−2ϵ_{k}) · \frac{1}{2} ln(2 − 2 cos ϵ_{k}) + cos(−2ϵ_{k}) tan^{−1} [\frac{sin ϵ_{k}}{1 − cos ϵ_{k}} ]]

(5)

for m = 4; but since B differs only in the sign of the logarithmic part of its sum, then A+B will cancel the logarithmic parts of the summation and so we must have

A + B = \frac{2\sqrt{3}}{9} · 2[\frac{7π}{18} cos \frac{4π}{9} + \frac{π}{18} cos \frac{16π}{9} − \frac{5π}{18} cos \frac{28π}{9} ].  (6)

Now taking the C sum with m = 1 we have

C = \frac{2\sqrt{3}}{9} ∑_{k=0}^{2} − sin(ϵ_{k}) · \frac{1}{2} ln(2 − 2 cos ϵ_{k}) + cos(ϵ_{k}) tan^{−1} [\frac{sin ϵ_{k}}{1 − cos ϵ_{k}} ]  (7)

= \frac{2\sqrt{3}}{9}[ − sin \frac{2π}{9} · \frac{1}{2} · ln(2 − 2 cos \frac{2π}{9} ) − sin \frac{8π}{9} · \frac{1}{2} ln(2 − 2 cos \frac{8π}{9} )

− sin \frac{14π}{9} · \frac{1}{2} ln(2 − 2 cos \frac{14π}{9} ) + \frac{7π}{18} · cos \frac{2π}{9} + \frac{π}{18} · cos \frac{8π}{9} − \frac{5π}{18} cos \frac{14π}{9} ].

And the D sum with m = 3 yields

D = \frac{2\sqrt{3}}{9} ∑_{k=0}^{2} [ − sin(−ϵ_{k}) · \frac{1}{2} ln(2 − 2 cos ϵ_{k}) + cos(−ϵ_{k}) tan^{−1} [\frac{sin ϵ_{k}}{1 − cos ϵ_{k}} ]]. (8)

As in (5), D differs only in the sign of the logarithmic part of its sum, and so C +D will cancel the logarithmic parts of the summation and you will have

C + D = \frac{2\sqrt{3}}{9} · 2[\frac{7π}{18} cos \frac{2π}{9} + \frac{π}{18} cos \frac{8π}{9} − \frac{5π}{18} cos \frac{14π}{9} ].  (9)

It now remains to show that

A + B = (C + D)α.

(6) may be simplified to

\frac{2\sqrt{3}π}{18} [5 cos \frac{π}{9} + 7 cos \frac{4π}{9} − cos \frac{7π}{9} ]  (10)

and now simplifying (9) and multiplying through by α we have

(C + D)α = \frac{2\sqrt{3}π}{81} [14 cos \frac{π}{9} cos \frac{2π}{9} + 2 cos \frac{π}{9} cos \frac{8π}{9} − 10 cos \frac{π}{9} cos \frac{14π}{9} ] (11)

= −7(cos \frac{6π}{9} + cos \frac{8π}{9} ) + cos \frac{7π}{9} − 1 + 5(cos \frac{4π}{9} + cos \frac{6π}{9} )

= \frac{7}{2} − 7 cos \frac{8π}{9} + cos \frac{7π}{9} − 1 + 5 cos \frac{4π}{9} − \frac{5}{2} = 7 cos \frac{π}{9} + 5 cos \frac{4π}{9} + cos \frac{7π}{9} .

This simplification was reached after using product and half-angle formulas from the Handbook of Mathematical Functions, edited by M. Abramowitz and Irene Stegun, Dover Publications, 9th ed. 1970, 4.3.32 and 4.3.36, p. 72, 73.

We now rewrite this last expression as

5 cos \frac{π}{9} + (2 cos \frac{π}{9} ) + 7 cos \frac{4π}{9} − (2 cos \frac{4π}{9} ) − cos \frac{7π}{9} + (2 cos \frac{7π}{9} ). (12)

It remains to show that

cos \frac{π}{9} − cos \frac{4π}{9} + cos \frac{7π}{9} = 0.  (13)

But

cos \frac{π}{9} − cos \frac{4π}{9} + cos \frac{7π}{9}

= cos \frac{π}{9} − cos \frac{π}{9} cos \frac{3π}{9} + sin \frac{π}{9} sin \frac{3π}{9} + cos \frac{π}{9} cos \frac{6π}{9} − sin \frac{π}{9} sin \frac{6π}{9}

= cos \frac{π}{9} − \frac{1}{2} cos \frac{π}{9} + \frac{\sqrt{3}}{2} sin \frac{π}{9} − \frac{1}{2} cos \frac{π}{9} − \frac{\sqrt{3}}{2} sin \frac{π}{9} = 0.

This completes the proof.

132. [1999,197] Proposed by Don Redmond, Southern Illinois University, Carbondale, Illinois.

Let F_{n} denote the nth Fibonacci number. That is, F_{0} = 0, F_{1} = 1 and for n ≥ 2, F_{n} = F_{n−1} + F_{n−2}. In 1883 Cesaro showed that

∑_{k=0}^{n} \binom{n}{k}F_{k} = F_{2n} and ∑_{k=0}^{n} \binom{n}{k}2^{k}F_{k} = F_{3n}.

Prove the following generalization of Cesaro’s result. Let r and s be roots of the quadratic equation

x^{2} − ax − b = 0.  (1)

Define the two sequences {P_{n}} and {Q_{n}} by

Q_{n} = \frac{r^{n} − s^{n}}{r − s} and P_{n} = cr^{n} + ds^{n},

where c and d are constants. If j ≥ 2, then

∑_{k=0}^{n} \binom{n}{k}(bQ_{j−1})^{n−k}Q_{j}^{k}P_{k} = P_{jn}.

Solution by the proposer. We begin with a lemma.

\underline{Lemma}. If x satisfies (1), then, for n ≥ 1,

x^{n} = Q_{n}x + bQ_{n−1}.

\underline{Proof}. It is clear that Q_{0} = 0, Q_{1} = 1, Q_{2} = a and that, for n ≥ 1,

Q_{n+1} = aQ_{n} + bQ_{n−1}.

We proceed by induction on n.

For n = 1 and 2 we have

x = Q_{1}x + bQ_{0} and x^{2} = ax + b = Q_{2}x + bQ_{1},

so that the result is true in these cases.

If we assume that the result is true for n = m ≥ 1, that is,

x^{m} = Q_{m}x + bQ_{m−1},

then, for n = m + 1, we have

x^{m+1} = x · x^{m} = x(Q_{m}x + bQ_{m−1}) = x^{2}Q_{m} + xbQ_{m−1}

= (ax + b)Q_{m} + xbQ_{m−1} = x(aQ_{m} + bQ_{m−1}) + bQ_{m}

= xQ_{m+1} + bQ_{m}

which is the result for n = m + 1 and the lemma follows.

We now prove the main result. We have

∑_{k=0}^{n} \binom{n}{k}(bQ_{j−1})^{n−k}Q_{j}^{k}P_{k} = ∑_{k=0}^{n} \binom{n}{k}(bQ_{j−1})^{n−k}Q_{j}^{k}(cr^{k} + ds^{k})

= c ∑_{k=0}^{n} \binom{n}{k}(bQ_{j−1})^{n−k}Q_{j}^{k}r^{k} + d ∑_{k=0}^{n} \binom{n}{k}(bQ_{j−1})^{n−k}Q_{j}^{k}s^{k}

= c(Q_{j}r + bQ_{j−1})^{n} + d(Q_{j}s + bQ_{j−1})^{n} = cr^{jn} + ds^{jn} = P_{jn},

by the lemma. The result follows.

Also solved by José Luis Díaz, Universidad Politécnica de Cataluña, Terrassa, Spain and Kenneth B. Davenport, 301 Morea Road, Box 491, Frackville, Pennsylvania.