Department of Math and Computer Science
Problems of the Month 1996

Proposed by Dan Jurca

Compute the product Õk=0n(x2k+1) as a function of x and n.

Proposed by Dan Jurca

There is a nonconstant function f:R®R   such that

i.

f(0)=2;

ii.

f is continuously differentiable;

iii.

for each positive X if S_X is the solid obtained by revolving about the x-axis the region bounded by the x-axis, the graph of f , and the vertical lines x=0 and x=X, then the surface area of S_X (excluding the circular ``ends'') equals the volume of S_X.

Proposed by Professor Stu Smith

For n=1,2,3,¼ let X_n be the continued fraction as follows.

Xn=a1+  1 a2+  \strut 1 a3+  \strut1 a4+  \strut 1 ···+\strut an-1+  1 an

Show that when X_n is written as a ``proper fraction'' (i.e., no fraction in numerator or denominator) the number of terms in both the numerator and the denominator are Fibonacci numbers (i.e., elements of the sequence 0,1,1,2,3,5,8,13,21,¼).

For example,

X4=  a1a2a3a4+a1a2+a1a4+a3a4+1 a2a3a4+a2+a4 ,

in which the numerator consists of 5 terms and the denominator consists of 3 terms.

Proposed by Dan Jurca

Prove that if m and n are integers, 0 £ m , and 1 £ n, then (n!)^mm! | (mn)!.

Remarks.

i.

The symbol `|' means ``divides''.

ii.

You might like to compute the quotient (which is, of course, asserted to be an integer).

iii.

The proposer recently came across a reference to this result in a Canadian mathematics magazine (the Crux Mathematicorum ), in which it was claimed to be ``well known''.

Since it was not well known to the proposer, the proposer wanted to prove it is true.

Solution by the proposer

Proposition: m,n Î Z, 0 £ m, 1 £ n Þ (n!)^mm! | (mn)!.

Proof.

The assertion clearly holds in the case m=0 and 1 £ n, so assume from now on that 1 £ m and 1 £ n.

Lemma 1: n,x Î Z, 1 £ n £ x Þ x(x-1)(x-2)¼[x-(n-1)]=n!(x || n).

Proof of lemma 1.

x(x-1)(x-2)¼[x-(n-1)] = [ x!/((x-n)!)]=n![ x!/(n!(x-n)!)]=n!(x || n),

proving lemma 1.

Remark: Hence n! divides the product of any n consecutive integers.

Lemma 2: m,n Î Z, 1 £ m, 1 £ n Þ (mn || n)=m((mn-1) || (n-1)).

Proof of lemma 2.

(mn || n)=[ (mn)!/(n!(mn-n)!)] = [((mn)(mn-1)!)/(n(n-1)!(mn-n)!)] = m[((mn-1)!)/((n-1)!(mn-n)!)]=m((mn-1) || (n-1)),

proving lemma 2.

We complete the proof by expressing (mn)!, the product of mn factors, as a product of m products, each of n consecutive integer factors, as follows:

(mn)! =(mn)·(mn-1)·(mn-2)· ¼ ·(2)·(1) = m Õ k=1  ì í î [(m+1-k)n]·[(m+1-k)n-1]· ¼ ·[(m+1-k)n-(n-1)] ü ý þ = m Õ k=1  n! æ è (m+1-k)n n ö ø , by lemma 1 =(n!)m m Õ k=1  æ è (m+1-k)n n ö ø =(n!)m m Õ k=1  (m+1-k) æ è (m+1-k)n-1 n-1 ö ø , by lemma 2 =(n!)mm! m Õ k=1  æ è (m+1-k)n-1 n-1 ö ø .

The last line above exhibits the integral quotient, completing the proof.

Also solved by Eric Leong.

Proposed by Dan Jurca

According to the 1996 April issue of the Canadian mathematics journal Crux Mathematicorum the following problem was given as part of the selection test for the Balkan Olympic Team (No, not those Olympics; rather the International Mathematics Olympiad).

Can you do it?

Prove that the sequence (Im(z_n))_n=1^¥ of the imaginary parts of the complex numbers z_n=(1+i)(2+i)¼(n+i) contains infinitely many positive and infinitely many negative numbers.

We have k+i=Ö{k²+1}×e^iq_k where q_k=tan^-11/_k; hence z_n=(Õ_k=1ⁿÖ{k²+1})×e^iq_n where q_n=å_k=1ⁿtan^-11/_k. One easily shows 1 £ k Þ [ 1/2k] < tan^-11/_k < ¹/_k. Hence with H_n=1+¹/₂+¹/₃+¼+¹/_n, the n-th partial sum of the (divergent) harmonic series, we have ¹/₂H_n < q_n < H_n. Thus for k=0,1,2,3,¼ $ n_k such that

1 £ n < nk Þ 0 £ qn £ kp;   kp < qnk < (k+1)p.

Clearly k even Þ 0 < Im(z_nk), k odd Þ Im(z_nk) < 0.

Remark: The first few n_k and q_nk are as follows:

q1 =qn0=0.2500000000p q17 =qn1=1.0072981352p q396 =qn2=2.0003604476p q9165 =qn3=3.0000203961p q212082 =qn4=4.0000001066p q4907734 =qn5=5.0000000129p

Also solved by Thomas Kim and Eric Leong.

Proposed by Dan Jurca

Find the exact value of    (Ö{50}+7)1/3-(Ö{50}-7)1/3.

Solution by the proposer

We show (Ö{50}+7)^1/3-(Ö{50}-7)^1/3=2.

More generally, suppose q Î R, the set of real numbers, and let

x=   æ Ö æ è  q3+3q 2 ö ø 2   +1    +  æ è  q3+3q 2 ö ø .

Then x ¹ 0 and one finds at once

y=  1 x =   æ Ö æ è  q3+3q 2 ö ø 2   +1    -  æ è  q3+3q 2 ö ø .

Observe that with q=2 we have x=(Ö{50}+7) and y=(Ö{50}-7).
Then

z=x1/3-y1/3=x1/3-  1 x1/3 =  x2/3-1 x1/3 =  x4/3-x2/3 x .

Also

z3=  x2-3x4/3+3x2/3-1 x =  x2-1 x -3  x4/3-x2/3 x =  x2-1 x -3z.

Finally

x2-1 x =x-  1 x =x-y=q3+3q.

Hence z³+3z-(q³+3q)=0, so (z-q)[z²+qz+(q²+3)]=0. Since z Î R, it follows that z=q. The proposed problem corresponds to the case q=2.

Remark: Probably the most interesting cases occur when, as in the present example, q Î Q⁺, the set of positive rationals. The proposer found (in a mathematics magazine) the problem corresponding to q=1.

Also solved by Walter Becker, Al Franz, Teruyuki Hiyama, Thomas Kim, Eric Leong, and Brad Stoll

Proposed by Eriko Hironaka (MSRI, Berkeley)

Communicated by Dan Jurca

Consider the ``half-Pascal's triangle'', the first seven rows of which appear as follows.

1

1      0

1      1      0

1      2      0      0

1      3      2      0      0

1      4      5      0      0      0

1      5      9      5      0      0      0

Show that the sum of the entries in the n-th row equals (n || (ën/2û)).

(The top row corresponds to n=0.)

Precisely, we define the array x of integers as follows:

xi,j= ì ï ï í ï ï î 1 if 0 £ i and j=0; xi-1,j-1+xi-1,j if 1 £ i and 1 £ j £ ëi/2û; 0 if 1 £ i and ëi/2û < j £ i.

Then:

0 £ i Þ  i å j=0  xi,j= æ è i ëi/2û ö ø .

First we define the array y for 0 £ i and 0 £ j £ i as follows.

yi,j= ì ï ï ï í ï ï ï î 1 if 0 £ i and j=0;  i-2j+1 j æ è i j-1 ö ø if 1 £ i and 1 £ j £ ëi/2û; 0 if 1 £ i and ëi/2û < j £ i.

Then, obviously, x_i,j=y_i,j if either 0 £ i and j=0, or if 1 £ i and ëi/2û < j £ i. Next, we show that if 1 £ i and 1 £ j £ ëi/2û, then x_i,j=y_i,j as well. One easily checks that x_1,0=y_1,0 and x_1,1=y_1,1; so suppose that 2 £ i. Then if j=1, we find y_i,j=y_i,1=(i-1)(i || 0)=i-1=1+(i-2)=y_i-1,0+y_i-1,1=y_i-1,j-1+y_i-1,j. Next, if 2 £ j £ ëi/2û, then 1 £ j-1 £ ëi/2û-1 £ ë(i-1)/2û; hence

yi,j =  i-2j+1 j æ è i j-1 ö ø =  i-2j+1 j  i! (j-1)!(i-j+1)! =  i-2j+1 j  i i-j+1  (i-1)! (j-1)!(i-j)! =  i(i-2j+1) (i-j+1)j æ è i-1 j-1 ö ø =  i2-2ij+i (i-j+1)j æ è i-1 j-1 ö ø =  ij-2j2+2j  +  i2-2ij-ij+2j2+i-2j (i-j+1)j æ è i-1 j-1 ö ø =  (i-2j+2)j  +  (i-j+1)(i-2j) (i-j+1)j æ è i-1 j-1 ö ø = é ë  i-2j+2 i-j+1 +  i-2j j ù û æ è i-1 j-1 ö ø =  i-2j+2 i-j+1  (i-1)! (j-1)!(i-j)! +  i-2j j æ è i-1 j-1 ö ø =  i-2j+2 j-1  (i-1)! (j-2)!(i-j+1)! +  i-2j j æ è i-1 j-1 ö ø =  i-2j+2 j-1 æ è i-1 j-2 ö ø +  i-2j j æ è i-1 j-1 ö ø =yi-1,j-1+yi-1,j.

It follows that for 0 £ i and 0 £ j £ i we have x_i,j=y_i,j.

Thus

0 £ i and 1 £ j £ ëi/2û Þ xi,j =  i-2j+1 j æ è i j-1 ö ø =-2 æ è i j-1 ö ø +  i+1 j æ è i j ö ø =-2 æ è i j-1 ö ø + æ è i+1 j ö ø .

The following identities follow at once from the well-known 0 £ i Þ å_j=0ⁱ(i || j)=2ⁱ and the symmetry of Pascal's triangle.

i even Þ  i/2-1 å j=0  æ è i j ö ø =2i-1-  1 2 æ è i i/2 ö ø i/2 å j=0  æ è i+1 j ö ø =2i i odd Þ  ëi/2û-1 å j=0  æ è i j ö ø =2i-1- æ è i ëi/2û ö ø ëi/2û å j=0  æ è i+1 j ö ø = 2i-  1 2 æ è i+1 (i+1)/2 ö ø =2i- æ è i ëi/2û ö ø .

Hence for even i :

i å j=0  xi,j = i/2 å j=0  xi,j =1+ i/2 å j=1  xi,j =1+ i/2 å j=1  é ë -2 æ è i j-1 ö ø + æ è i+1 j ö ø ù û =-2 i/2-1 å j=0  æ è i j ö ø + i/2 å j=0  æ è i+1 j ö ø =-2 é ë 2i-1-  1 2 æ è i i/2 ö ø ù û +2i = æ è i i/2 ö ø ;

and for odd i :

i å j=0  xi,j = ëi/2û å j=0  xi,j =1+ ëi/2û å j=1  xi,j =1+ ëi/2û å j=1  é ë -2 æ è i j-1 ö ø + æ è i+1 j ö ø ù û =-2 ëi/2û-1 å j=0  æ è i j ö ø + ëi/2û å j=0  æ è i+1 j ö ø =-2 é ë 2i-1- æ è i ëi/2û ö ø ù û +2i- æ è i ëi/2û ö ø = æ è i ëi/2û ö ø

Thus 0 £ i Þ å_j=0ⁱx_i,j=(i || (ëi/2û)), as asserted.

Also solved by the proposer (in an entirely different and quite ingenious way).

Proposed anonymously

From an observation by Vladimir Arnol'd

Determine whether

lim x®0     tan(sinx)-sin(tanx) arctan(arcsinx)-arcsin(arctanx)

exists; if it exists, determine its value.

Solution by Dan Jurca

We show the limit exists and equals 1.

One can find these well-known expansions in various tables:

tanx =x+  x3 3 +  2x5 15 +  17x7 315 +  62x9 2835 +¼ sinx =x-  x3 3! +  x5 5! -  x7 7! +  x9 9! +¼ arctanx =x-  x3 3 +  x5 5 -  x7 7 +  x9 9 -¼ arcsinx =x+  1·x3 2·3 +  1·3·x5 2·4·5 +  1·3·5·x7 2·4·6·7 +  1·3·5·7·x9 2·4·6·8·9 +¼

By the analyticity of each of these functions at 0, and by the analyticity of the composition of analytic functions, we may substitute (for example) the series for sinx into the series for tanx and obtain

tan(sinx))=x+  x3 6 -  x5 40 -  107x7 5040 -  73x9 24192 +¼

(The solver wrote a computer program to do the (tedious) calculations.)

Similarly

sin(tanx)) =x+  x3 6 -  x5 40 -  55x7 1008 -  143x9 3456 +¼ arctan(arcsinx)) =x-  x3 6 +  13x5 120 -  173x7 5040 +  12409x9 362880 +¼ arcsin(arctanx)) =x-  x3 6 +  13x5 120 -  341x7 5040 +  18649x9 362880 +¼

Substituting these expansions we find that for x near to (but different from) 0:

tan(sinx)-sin(tanx) arctan(arcsinx)-arcsin(arctanx) =  1 30 x7+  29 756 x9+¼  1 30 x7-  13 756 x9+¼ =1+  5 3 x2+¼

so that the limit exists and equals 1, as asserted.

Proposed by Dan Jurca

Suppose that the rational function (quotient of polynomials) p(x)/q(x) nicely approximates the function e^x for small x, in the sense that

p(x) q(x) =1+x+  x2 2! +  x3 3! +¼+  xN N! +O(xN+1).

Assume that

p(x)= m å i=0  aixi,       q(x)= n å i=0  bixi,

and we define

- p   (x)= m å i=0  - a   i  xi,       - q   (x)= n å i=0  - b   i  xi,

where

- a   i  = ì ï í ï î ai for i even; -ai for i odd;    and    - b   i  = ì ï í ï î bi for i even; -bi for i odd.

Show that [([`q](x))/([`p](x))] approximates e^x equally well; i.e.,

- q   (x) - p   (x) =1+x+  x2 2! +  x3 3! +¼+  xN N! +O(xN+1).

For example, we find

720+600x+240x2+60x3+10x4+x5 720-120x =1+x+  x2 2! +  x3 3! +  x4 4! +  x5 5! +  x6 6! +O(x7);  720+120x 720-600x+240x2-60x3+10x4-x5 =1+x+  x2 2! +  x3 3! +  x4 4! +  x5 5! +  x6 6! +O(x7).

Solution by the proposer

We remark that the rational approximation of e^x given in the problem is an instance of a Padé approximation; and in the special case of the exponential function the Padé approximation of bidegree (m,n) is explicitly known [1, page 24]:

ex »  p(x) q(x) = m å i=0  æ è m i ö ø (m+n-i)! xi n å i=0  æ è n i ö ø (m+n-i)! (-x)i ,

from which the assertion of the problem follows at once. We can prove a somewhat more general result:

Proposition. Suppose f is an analytic function in some neighborhood of 0 and for x in that neighborhood

f(x)=1+x+  x2 2! +  x3 3! +  x4 4! +¼+  xn n! + é ë  1 (n+1)! -e ù û xn+1+¼.

Then with y(x)=[ 1/(f(-x))] we have, in a neighborhood of 0,

y(x)=1+x+  x2 2! +  x3 3! +  x4 4! +¼+  xn n! + é ë  1 (n+1)! -(-1)ne ù û xn+1+¼.

Before proving this proposition, we remark that there are indeed such approximations of e^x which are not rational functions, for example (the silly)

ex »   æ Ö  1+x 1-x   =1+x+  x2 2 +  x3 2 +¼ = 1+x+  x2 2! + é ë  1 3! -(-  1 3 ) ù û x3+¼.

Also the proposition gives the assertion of the problem, where

f(x)=  p(x) q(x) , and y(x)= - q   (x) - p   (x) =  q(-x) p(-x) =  1 f(-x) .

Proof of proposition. First we observe the well-known

1 £ i Þ  i å j=0  (-1)j æ è i j ö ø = i å j=0  æ è i j ö ø 1i-j(-1)j=[1+(-1)]i=0i=0.

(*)

Then we recall Leibniz's formula, easily proved by induction:
Suppose for 0 £ i that there exist i derivatives of u and of v ; then there exist i derivatives of the product uv , and moreover (uv)⁽ⁱ⁾=å_j=0ⁱ(i || j) u^(i-j)v^(j)                                      (**)
where ^(k) denotes k-th derivative.
By hypothesis f(-x)y(x)=1, at least for x near 0. Clearly 0 £ i £ n Þ f⁽ⁱ⁾(0)=1; we shall show that the same holds for y⁽ⁱ⁾(0).

Observe first that from f(0)y(0)=1 we have y(0)=1; assume (inductively) 1 £ i £ n,
and 0 £ j < i Þ y^(j)(0)=1. By the chain rule 0 £ i Þ [f(-x)]⁽ⁱ⁾=(-1)ⁱf⁽ⁱ⁾(-x).
By (**)

1 £ i £ n Þ [f(-x)y(x)](i)=1(i)=0 = i å j=0  æ è i j ö ø [f(-x)](i-j)y(j)(x) = i å j=0  æ è i j ö ø (-1)i-jf(i-j)(-x)y(j)(x).

Then with x=0 we find, since f^(i-j)(0)=1, that å_j=0ⁱ(i || j)(-1)^i-jy^(j)(0)=0.

Hence

1 £ i £ n Þ y(i)(0) =(-1)i-1 i-1 å j=0  (-1)j æ è i j ö ø y(j)(0) =(-1)i-1 i-1 å j=0  (-1)j æ è i j ö ø    by inductive hypothesis =(-1)i-1·(-1)i-1         by (*) =1.

Thus

0 £ i £ n Þ y(i)(0)=1.

(***)

By (**) again we have

n+1 å j=0  æ è n+1 j ö ø [f(-x)](n+1-j)y(j)(x)=0,

whence

y(n+1)(0) =-(-1)n+1f(n+1)(0)- n å j=1  æ è n+1 j ö ø (-1)n+1-j =(-1)nf(n+1)(0)-(-1)n+1 n å j=1  (-1)j æ è n+1 j ö ø =(-1)nf(n+1)(0)-(-1)n+1·[-1-(-1)n+1] =(-1)nf(n+1)(0)+(-1)n+1+1.

from which one easily completes the proof of the proposition.

[1]

D.J.Newman, Approximation with Rational Functions, Conference Board of the Mathematical Sciences, Number 41, American Mathematical Society, Providence, Rhode Island, 1978

Proposed by Dan Jurca

Suppose that n is a non-negative integer, r Î R, and 1 < |r|; then (by the ratio test) å_i=1^¥ [(iⁿ)/(rⁱ)] converges; find a formula, or practical method, to evaluate the sum precisely.

Solution by the proposer

For a fixed r Î R, 1 < |r| we write, for non-negative integers n: S_n=å_i=1^¥[(iⁿ)/(rⁱ)]. Then

S0= ¥ å i=1   1 ri =  1/r 1-1/r =  1 r-1 .

Now suppose 1 £ n; we shall compute S_n in terms of S₀, S₁,¼,S_n-1 as follows.

Sn= ¥ å i=1   in ri

so that

rSn = ¥ å i=1   in ri-1 = ¥ å i=0   (i+1)n ri = ¥ å i=0  n å j=0  æ è n j ö ø ij·  1 ri = n å j=0  æ è n j ö ø ¥ å i=0   ij ri = n å j=0  æ è n j ö ø Sj = n-1 å j=0  æ è n j ö ø Sj + Sn.

Therefore

(r-1)Sn = n-1 å i=0  æ è n i ö ø Si, whence Sn =  1 r-1 · n-1 å i=0  æ è n i ö ø Si,

from which each S_n may be computed recursively.