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: 3² + 4² = 25 = 5²,  and  n = 3: 3³ + 4³ + 5³ = 216 = 6³.

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

L_n = 3ⁿ + 4ⁿ+ ... + (n+2)ⁿ  and  Rn = (n+3)ⁿ.

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

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, L_n < R_n.

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-1 + ¹/₂ 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)²(r + 2)^r–2 + r(r + 2)(r + 2)^{r –2} + ¹/₂ r(r - 1)(r + 2)^r-2 
                     > 2(r + 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

r² - 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 L_n < R_n for small values of n, so we now assume that we have established that L_n < R_n for all values of n up to some k ≥ 5; that is, we assume that

3^k + 4^k + ... + (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)(3^k + 4^k + ... + (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

3^k+1 + 4^k+1 + ... + (k + 3)^k+1< (k + 3)(3^k + 4^k + ... + (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, L_n < R_n for all n ≥ 4.