Department of Math and Computer Science
Problems of the Month 2000

Proposed by Dan Jurca

Prove that if z Î C and 1 < |z|, then

¥ å n=1   1 zn+1  +  ¥ å n=1   (-1)n zn-1 =0.

We shall prove a more general result. Precisely, we show

z Î C and 1 < |z| Þ  ¥ å n=1   1 zn+1  +  ¥ å n=1   (-1)n zn-1 =0.

For if 1 < |z|, then 1 £ d Þ

1 zd+1 =  z-d 1+z-d =  z-d 1-(-z-d) =z-d-z-2d+z-3d-z-4d+-¼ =- ¥ å q=1  (-1)qz-dq,   and  (-1)d zd-1 =(-1)d  z-d 1-z-d =(-1)d(z-d+z-2d+z-3d+z-4d+¼) =(-1)d ¥ å q=1  z-dq.

Hence 1 < |z| Þ

¥ å n=1   1 zn+1  +  ¥ å n=1   (-1)n zn-1 = ¥ å d=1   1 zd+1  +  ¥ å d=1   (-1)d zd-1 = ¥ å d=1  é ë - ¥ å q=1  (-1)qz-dq + (-1)d ¥ å q=1  z-dq ù û = ¥ å d=1  ¥ å q=1  é ë (-1)d-(-1)q ù û z-dq = ¥ å n=1  å d|n  é ë (-1)d-(-1)n/d ù û z-n =0,   since a Î C, 1 £ n Þ  å d|n  (ad-an/d) =0.

Also solved by Ed Keller, Massoud Malek, and John M. Sayer.

Proposed by Dan Jurca

This two-part problem involves b_n, the number of binary trees with n nodes (0 £ n), so may interest students of computer science. Recall

b0 =1 b1 =1 b2 =2 b3 =5,

and more generally one may compute b_n recursively as follows

b0 =1, 1 £ n Þ bn = n-1 å i=0  bibn-1-i,

or using the closed formula

0 £ n Þ bn=  1 n+1 æ è 2n n ö ø .

a.

Show that b_n equals an odd integer if and only if there exists a nonnegative integer p such that n=2^p-1.

b.

The table printed below shows the time required to calculate b_n for the first few values of n using a C program, also shown below, which evaluates b_n recursively. Examination of the table shows that if 3 £ n, then the time to compute b_n closely approximates 3 times the time to compute b_n-1. Explain this.

(The proposer compiled this program with the GNU compiler, and ran it under Red Hat Linux version 6.1 on a computer with a 200 MHz Pentium Pro microprocessor. Here ``usec'' means ``microsecond''.)

a.

We shall prove the assertion by induction on n, observing that it hold for n £ 5. Suppose that 6 £ n and that 0 £ m < n Þ b_m equals an odd integer if and only if there exists q such that m=2^q-1. Assume first that b_n equals an odd integer. Using the inductive hypothesis we have

bn = n-1 å i=0  bibn-1-i º b0bn-1+b1bn-2+b3bn-4+b7bn-8+¼+bn-2b1+bn-1b0   (mod 2).

Now b_i º 1 (mod 2) if and only if i=2^j-1, and b_n-1-i º 1 (mod 2) if and only if n-1-i=2^k-1. Hence each term in the sum above equals 0 (mod 2) unless n=2^j+2^k-1 for some j and k. Since, by assumption, b_n º 1 (mod 2), there do exist j and k such that n=2^j+2^k-1. Now if j ¹ k, then the summation has two equal terms which therefore cancel mod 2, so it follows that j=k. Hence n=2^j+2^j-1 = 2^j+1-1, so that the assertion holds also for n.
Next, if n=2^p-1, 2 £ p, then since b_n=å_i=0^n-1b_ib_2^p-2-i, the only terms which contribute an odd value to the sum are those for which i=2^j-1, some j, and 2^p-2-i=2^p-2^j-1=2^k-1, some k; i.e., 2^p=2^j+2^k. Then j=k=p-1, so the only term which contributes an odd value to the sum is the one with i=2^p-1-1, so that b_n equals an odd integer.

b.

Suppose evaluation of b_n requires time t_n. Study of the code shows that for some constants a, b, and c

t0=t1 =a, 2 £ n Þ tn =2 n-1 å i=0  ti + bn + c.

Eliminating the recursion one finds (and checks by induction on n)

2 £ n Þ tn=(4a+5b/2+c)3n-2-b/2,

so that with A=(4a+5b/2+c)/9 and B=b/2 we have

2 £ n Þ tn=A·3n-B.

No other solution was received.

Find the sum of the first n terms of the following series.

12+22+42+72+112+162+222+292+372+462+562+¼

Solution by the proposer

We write S_n for the sum of the first n terms; then

Sn = n å i=1  ai2,   where ai =  i2-i+2 2 .

(The differences between consecutive a_i make an arithmetic series, so that a_i equals some quadratic in i; one finds easily that the above formula holds for a_i.)
Hence

Sn = n å i=1  é ë  i2-i+2 2 ù û 2   =  1 4 n å i=1  (i4-2i3+5i2-4i+4) =  1 4 n å i=1  i4-  1 2 n å i=1  i3+  5 4 n å i=1  i2- n å i=1  i+ n å i=1  1 =  6n5+15n4+10n3-n 120 -  n4+2n3+n2 8 +  10n3+15n2+5n 24 -  n2+n 2 +n =  6n5+30n3+84n 120 =  n5+5n3+14n 20 .

Also solved by William Loewe, John Sayer, and Professor Ed Keller

proposed by Dan Jurca

a.

Prove that if n is an integer and 2 £ n, then

1 2 < æ è 1-  1 4 ö ø · æ è 1-  1 9 ö ø · æ è 1-  1 16 ö ø · ¼ · æ è 1-  1 n2 ö ø .

b.

Determine

lim n®¥  æ è 1-  1 4 ö ø · æ è 1-  1 9 ö ø · æ è 1-  1 16 ö ø · ¼ · æ è 1-  1 n2 ö ø .

Solution by the proposer

For 2 £ n write

pn= æ è 1-  1 4 ö ø · æ è 1-  1 9 ö ø · æ è 1-  1 16 ö ø · ¼ · æ è 1-  1 n2 ö ø ;

then we show by induction that

2 £ n Þ pn=  1 2 +  1 2n .

Since p₂=1-¹/₄=³/₄=¹/₂+¹/₄=¹/₂+[ 1/2·2], the assertion certainly holds if n=2.

Next assume 3 £ n, and p_n-1=¹/₂+[ 1/(2(n-1))]. Then

pn =pn-1· æ è 1-  1 n2 ö ø = æ è  1 2 +  1 2n-2 ö ø ·  n2-1 n2 =  1 2 · æ è 1+  1 n-1 ö ø ·  (n-1)(n+1) n2 =  1 2 ·  n n-1 ·  (n-1)(n+1) n2 =  1 2 ·  n+1 n =  1 2 +  1 2n ,

so the assertion holds by induction on n.

Part a. now follows at once, and clearly lim_n®¥p_n=¹/₂; in fact (p_n)_n=2^¥¯¹/₂.

Also solved by Matthew Hubbard, John M. Sayer, Dr. Louis Villanueva, and Professor Bill Nico

proposed by Dan Jurca

Recall the following notation.

1 £ N Þ HN= N å n=1   1 n ,

the N-th partial sum of the harmonic series, and let H₀=0.

Now suppose that a and b are integers, and that 0 < a < b.

a.

Prove that

¥ å n=0   1 (n+a)(n+b) =  1 b-a æ è Hb-1-Ha-1 ö ø .

b.

Call the sum above S(a,b); prove that there exists a polynomial p(x) with integer coefficients and degree b-a such that

0 £ N Þ  N å n=0   1 (n+a)(n+b) =S(a,b)-  1 b-a ·  p¢(N) p(N) ,

where p¢ is the derivative of p.

0 £ N Þ  N å n=0   b-a (n+a)(n+b) = N å n=0  æ è  1 n+a -  1 n+b ö ø = b-a-1 å n=0  æ è  1 n+a -  1 n+b ö ø + N å n=b-a  æ è  1 n+a -  1 n+b ö ø = b-a-1 å n=0   1 n+a - b-a-1 å n=0   1 n+b + N å n=b-a   1 n+a - N å n=b-a   1 n+b = b-a-1 å n=0   1 n+a - 2b-2a-1 å n=b-a   1 n+a + N å n=b-a   1 n+a - N å n=b-a   1 n+b = b-a-1 å n=0   1 n+a + N å n=2b-2a   1 n+a - N å n=b-a   1 n+b = b-a-1 å n=0   1 n+a + N å n=2b-2a   1 n+a - N+b-a å n=2b-2a   1 n+a = b-a-1 å n=0   1 n+a - N+b-a å n=N+1   1 n+a = b-a-1 å n=0   1 n+a - N å n=N+a-b+1   1 n+b .

(This may also be checked by induction on N.) Now the second summation is the sum of b-a terms, so clearly approaches 0 as N®¥. Hence

¥ å n=0   b-a (n+a)(n+b) = b-a-1 å n=0   1 n+a =  1 a +  1 a+1 + ¼ +  1 b-1 =Hb-1-Ha-1,

so dividing by (the non-zero) b-a yields a.

Now define

p(x) = b-a Õ i=1  (x+a+i) =(x+a+1)·(x+a+2)· ¼ ·(x+b),

so that p(x) is an integer polynomial of degree b-a. Then, by the product rule,

p¢(x)= b-a å i=1  Õ [(1 £ j £ b-a) || (j ¹ i)]  (x+a+j).

But since

N å n=0   b-a (n+a)(n+b) = b-a+1 å n=0   1 n+a - N å n=N+a-b+1   1 n+b =(b-a)S(a,b)- N å n=N+a-b+1   1 n+b ,

and

N å n=N+a-b+1   1 n+b =  1 N+a+1 +  1 N+a+2 + ¼ +  1 N+b =  p¢(N) p(N) ,

we have also the result asserted in b.

Also solved by John M. Sayer.

proposed by Dan Jurca

The n-simplex \triangleⁿ may be defined as follows.

\trianglen={(x0,x1,¼,xn) Î Rn+1 | 0 £ i £ n Þ 0 £ xi, and x0+x1+¼+xn=1}

The sketch below shows \triangle⁰=A, \triangle¹=AB, \triangle²=ABC; \triangle³ is a tetrahedron in R⁴.

Let us say that the 0-volume of a finite set of points is the number of points in the set, the 1-volume of a line segment is the length of the segment, the 2-volume of a polygonal region is the area of the region, the 3-volume of a polyhedron is the ordinary volume, etc.

Find a formula for the n-volume of \triangleⁿ.

Writing V_n for the n-volume of \triangleⁿ we show by induction on n that 0 £ n Þ V_n=Ö{n+1}/n!. This clearly holds if n=0 (for \triangle⁰ is a set consisting of a single point), or n=1 (for \triangle¹ is a line segment of length Ö2), or n=2 (for \triangle² is the closed region bounded by an equilateral triangle of side Ö2). So suppose that 2 £ n and V_n-1=Ön/(n-1)!. The following figure

To complete the argument by induction we need to determine h_n. Now h_n is the distance from the point (0,0,¼,0,1) Î Rⁿ⁺¹ to \triangle^n-1, which may clearly be assumed to be a subset of Rⁿ⁺¹ as well as of Rⁿ. Thus h_n is the distance from (0,0,¼,0,1) to \triangle^n-1={(x₀,x₁,¼,x_n-1,0) | 0 £ x_i and x₀+x₁+¼+x_n-1=1}. We may compute this distance by minimizing the square of the distance from the apex, (0,0,¼,0,1), to the points in \triangle^n-1. So consider

f(x0,x1,¼,xn-2) =x02+x12+¼+xn-12+1 =x02+x12+¼+(1-x0-x1-¼-xn-2)2+1.

Computing the partial derivatives of f with respect to the x_i we have

¶f ¶xi (x0,x1,¼,xn-2) =2xi+2(1-x0-x1-¼-xn-2)·-1 =2xi-2+2x0+2x1+¼+2xn-2,

so setting each of these n-1 partial derivatives to zero yields the following (n-1)×(n-1) linear system.

é ê ê ê ê ê ê ê ê ê ë 2 1 1 ¼ 1 1 2 1 ¼ 1 1 1 2 ¼ 1 : : : ··· : 1 1 1 ¼ 2 ù ú ú ú ú ú ú ú ú ú û é ê ê ê ê ê ê ê ê ê ë x0 x1 x2 : xn-2 ù ú ú ú ú ú ú ú ú ú û = é ê ê ê ê ê ê ê ê ê ë 1 1 1 : 1 ù ú ú ú ú ú ú ú ú ú û

The coefficient matrix, say A, above is nonsingular. In fact the determinant equals n. This may be verified by observing that A has the following n-1 linearly independent eigenvectors.

v1 =(1,1,1,¼,1)T v2 =(1,-1,0,0,¼,0,0)T v3 =(1,0,-1,0,¼,0,0)T v4 =(1,0,0,-1,¼,0,0)T : vn-1 =(1,0,0,0,¼,0,-1)T,

with associated eigenvalues n,1,1,1,¼,1. Therefore there exists a unique solution of the linear system; by inspection it is x_i=1/n, for i=0,1,¼,n-2. It follows that h_n, the distance from the apex (0,0,¼,0,1) of \triangleⁿ to its base \triangle^n-1, is equal to the distance in Rⁿ⁺¹ from the point (0,0,¼,0,1) to the point (1/n,1/n,¼,1/n,0), which equals

hn = Ö   (1/n)2+(1/n)2+¼+(1/n)2+1   = Ö   1/n+1   =   æ Ö  n+1 n   .

We can now complete the inductive argument.

Vn =  1 n hnVn-1 =  1 n ×   æ Ö  n+1 n   ×  Ön (n-1)! = Ö n+1 n! ,

as asserted.

It may be interesting to observe that (V_n)_n=0^¥®0 quite rapidly, and (h_n)_n=1^¥®1.

Also solved by John M. Sayer

communicated by Dan Jurca

The following problems are taken from the delightful Conjecture and Proof by Miklós Laczkovich. The first concerns the Fermat numbers F_n, and the second concerns the numbers F_n+2.

The Fermat number F_n is 2²ⁿ+1 where n is a non-negative integer. Thus

F0 =3 F1 =5 F2 =17 F3 =257 F4 =65,537

It is easy to show that F₀, F₁, F₂, F₃, and F₄ are primes, and Pierre Fermat conjectured around 1640 that each F_n is prime. However, in 1732 Euler found that 641 divides F₅; in fact F₅=4,294,967,297=641×6,700,417; in 1880 it was found that 274,177 divides F₆; and in 1970 it was found that F₇ is the product of two primes consisting of 17 and 22 decimal digits, respectively. It is now known that F_n is composite if 5 £ n £ 24; no Fermat prime is known beyond F₄. Gauss showed that the regular n-gon is constructible with unmarked straightedge and compass if and only if n equals a power of 2 times a product of distinct Fermat primes.

1.

Show that if 2 £ n, then F_n º 7(mod 10); i.e., show that if 2 £ n, then when F_n is written in base 10 the last digit is a 7.

2.

Write G_n=F_n+2, so that G_n=2²ⁿ+3. Show that there exist infinitely many n such that G_n is composite.

Solution by Dan Jurca

Each assertion can be proved by mathematical induction.

1.

First we observe

1 £ n Þ Fn =22n+1 =22n-1×2+1 =(22n-1)2+1 =(Fn-1-1)2+1 =Fn-12-2Fn-1+2.

Now F₂=17; if 3 £ n and F_n-1 º 7(mod 10), then there exists some integer q such that F_n-1=10q+7, and then

Fn =Fn-12-2Fn-1+2 =(10q+7)2-2(10q+7)+2 =100q2+140q+49-20q-14+2 =100q2+120q+37 =10(10q2+12q+3)+7,

so that F_n º 7(mod 10) as well. Hence by induction on n: 2 £ n Þ F_n º 7(mod 10).

2.

We shall show that 0 £ k Þ 7|G_2k+3.

This is immediate if k=0, since G₃=2²³+3=2⁸+3=256+3=259=7×37.

Next we observe

1 £ n Þ Gn =22n+3 =22n-1×2+3 =(22n-1)2+3 =(Gn-1-3)2+3 =Gn-12-6Gn-1+12,      so that 2 £ n Þ Gn =(Gn-22-6Gn-2+12)2-6(Gn-22-6Gn-2+12)+12 =Gn-24-12Gn-23+54Gn-22+222Gn-2+84 =(Gn-23-12Gn-22+54Gn-2+222)Gn-2+84.

Then since 7|84, we have 2 £ n and 7| G_n-2 Þ 7|G_n. Thus by induction on k we have 0 £ k Þ 7|G_2k+3, as asserted.

Therefore G_n is composite-indeed, divisible by 7-for infinitely many n.

Prove:       If   [ a/(b-c)]+[ b/(c-a)]+[ c/(a-b)]=0,    then    [ a/((b-c)²)]+[ b/((c-a)²)]+[ c/((a-b)²)]=0.

From the first equation we have

a (b-c)2 =-  b (b-c)(c-a) -  c (b-c)(a-b) = -  b(a-b)+c(c-a) (a-b)(b-c)(c-a) =-  ab-b2+c2-ac (a-b)(b-c)(c-a)  b (c-a)2 =-  a (c-a)(b-c) -  c (c-a)(a-b) = -  a(a-b)+c(b-c) (a-b)(b-c)(c-a) =-  a2-ab+bc-c2 (a-b)(b-c)(c-a)  c (a-b)2 =-  a (a-b)(b-c) -  b (a-b)(c-a) = -  a(c-a)+b(b-c) (a-b)(b-c)(c-a) =-  ac-a2+b2-bc (a-b)(b-c)(c-a)

so that by adding we obtain the asserted result:

a (b-c)2 +  b (c-a)2 +  c (a-b)2 =0.

Also solved by Dan Jurca, Stu Smith, and Dangthu Ta.

Proposed by Dan Jurca

For n=0, 1, 2, 3, ¼ the Pascal matrix P_n is the (n+1)×(n+1) matrix

Pn=(pij)0 £ i £ n,0 £ j £ n   where pij is the binomial coefficient  æ è i+j i ö ø .

For example,

P4= æ ç ç ç ç ç ç ç ç ç è 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø

Compute the determinant det(P_n) of P_n.

Row reduce from bottom up; i.e., subtract row n-1 from row n, then row n-2 from row n-1, etc., and finally row 0 from row 1. Then column reduce from right to left; i.e., subtract column n-1 from column n, then column n-2 from column n-1, etc., and finally column 0 from column 1. To see the result, let Q_n be the following (n+1)×(n+1) matrix.

æ ç ç ç ç ç ç ç ç ç ç ç ç ç è 1 0 0 ¼ 0 0 0 -1 1 0 ¼ 0 0 0 0 -1 1 ¼ 0 0 0 ¼ ¼ ··· ··· ¼ ¼ ¼ 0 0 0