Math Central - mathcentral.uregina.ca
Problem of the Month
 Currentproblem Recent problemswith solutions
 Older problems from 2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

Solution for January 2008

 The Problem: What are the positive integers n for which 3n + 4n+ ... + (n+2)n= (n+3)n?

Correct responses:

Correct submissions submitted by:

 Saïd Amghibech (Quebec) Matthew Lim ((USA) Timothy Calford (Ontario) Jacques Mertzeisen (France) Dan Dima (Romania) Viktor Pačnik  (Slovenia) Philippe Fondanaiche (France) John T. Robinson (USA) Xavier Hecquet (France) Heri Setiyawan (Indonesia)

The solution:

The equality holds only for n equal 2 and 3.  Although every correspondent got the correct answer, several of the arguments that accompanied their solutions were incomplete.  The details seem to have been a bit tricky this month.
One easily checks that the equality holds for n=2 and 3:

n = 2: 32 + 42 = 25 = 52,  and  n = 3: 33 + 43 + 53 = 216 = 63.

To get a feeling for why it fails to hold for any other value of n, let us denote the left and right sides of the equation by

Ln = 3n + 4n+ ... + (n+2)n  and  Rn = (n+3)n.

For n = 1, L1 = 1 and R1 = 4, and we observe that the left side is smaller.  Then comes 2 and 3 where the left and right sides are equal.  Then

 n Ln Rn 4 2258 2401 5 28975 32768 6 446899 531441 7 8080296 10000000

Note that for n > 3 the right side is not only larger, but it seems to be growing much faster than the left side.  This suggests that induction would be helpful here.  The claim we want to establish is

For n ≥ 4, Ln < Rn.

All the correct submissions proved this claim in essentially the same way.  We use here Mertzeisen's argument, simplified somewhat by a couple of nice ideas from Hecquet.

Lemma. If r ≥ 7 then (r + 3)r > 2(r + 2)r.

Proof. (r + 3)r  = ((r + 2) + 1)r> (r + 2)r + r(r + 2)r-11/2 r(r - 1)(r + 2)r-2.  (The inequality arises from stopping the binomial expansion of ((r+2) + 1)r after the third term.) We will show that this last sum exceeds 2(r + 2)r when r ≥ 7; that is (after rewriting it a bit),

Claim: (r + 2)2(r + 2)r–2 + r(r + 2)(r + 2)r –21/2 r(r - 1)(r + 2)r-2
> 2(r + 2)2(r + 2)r–2.

Since (r + 2) is positive, we can divide both sides by (r + 2)r–2 and reduce what is left to

r2 - 5r - 8 = (r - 7)(r + 2) + 6 > 0,

which is certainly true for r ≥ 7, thereby proving the claim.
We are now ready for our induction argument.  We have established that Ln < Rn for small values of n, so we now assume that we have established that Ln < Rn for all values of n up to some k ≥ 5; that is, we assume that

3k + 4k + ... + (k + 2)k < (k + 3)k                                          (1)

We must prove that (1) implies that the inequality also holds for n = k + 1.  Add (k + 3)k to both sides of equation (1) and multiply the resulting sums by (k + 3):

(k + 3)(3k + 4k + ... + (k + 2)k + (k + 3)k) < 2(k + 3)k+1                         (2)

Since k + 3 is at least as large as any of the numbers on the left that are being raised to the kth power, we derive from (2) that

3k+1 + 4k+1 + ... + (k + 3)k+1< (k + 3)(3k + 4k + ... + (k + 3)k) < 2(k + 3)k+1,

while from the lemma (with r = k + 1 and k ≥ 6) we have

2(k + 3)k+1< (k + 4)k+1.

Therefore, by induction, Ln < Rn for all n ≥ 4.

 Math Central is supported by the University of Regina and the Pacific Institute for the Mathematical Sciences.
 about math central :: site map :: links :: notre site français