Sum of First N Positive Integers Making a Perfect Square

Date: 02/28/2006 at 03:27:48
From: Andrei
Subject: For what values is 1+2+3+....+n   in a form such as  k^2

For what integer values of n and k does 1+2+3+...+n = k^2?

Date: 02/28/2006 at 11:26:16
From: Doctor Vogler
Subject: Re: For what values is 1+2+3+....+n   in a form such as  k^2

Hi Andrei,

Thanks for writing to Dr. Math.  That's a good question.  It's not
easy to answer, and its answer involves a lot of advanced math.

First of all, you may already know the formula for the sum of the
first n positive integers,

  1 + 2 + 3 + ... + n = n(n+1)/2.

This is easy to prove using induction, or using the trick of adding up
the sequence twice in opposite directions.  So I won't belabor this part.

So your question amounts to finding all pairs of positive integers
that satisfy the equation

  n(n+1)/2 = k^2.

When you want integer solutions to a (polynomial) equation, that is
called a Diophantine equation.  Linear Diophantine equations (i.e. the
polynomials have degree 1) are fairly simple.  But yours is quadratic
(polynomials of degree 2), which is quite a bit harder, but not yet in
the realm of impossibility.  Nearly all such quadratic Diophantine
equations are related to a Pell equation, and there is a lot of math
that goes into Pell equations.  You can see some of it in our
archives, such as

  Solving with the Pell Equation
    http://mathforum.org/library/drmath/view/66869.html 

and

  Solving Quadratic Diophantine and Pell Equations
    http://mathforum.org/library/drmath/view/66725.html 

Your equation becomes a Pell equation when you rearrange it like so:

  n(n+1) = 2k^2

  4n^2 + 4n = 8k^2

  (2n + 1)^2 - 2(2k)^2 = 1.

Then the associated Pell equation is

  x^2 - 2y^2 = 1

where x = 2n + 1 and y = 2k.  You might notice that you only want
solutions to the Pell equation where x is odd and y is even, but it
turns out that all solutions have this property (which isn't terribly
hard to prove).

It takes a lot more math to determine that every solution in positive
integers to

  x^2 - 2y^2 = 1

can, in fact, be written as

  x + y*sqrt(2) = (1 + sqrt(2))^(2m),

which is the same as

  x + y*sqrt(2) = (3 + 2*sqrt(2))^m,

for some positive integer m.

So you can either solve for x and y like so:

  x = ((3 + 2*sqrt(2))^m + (3 - 2*sqrt(2))^m)(1/2)
  y = ((3 + 2*sqrt(2))^m - (3 - 2*sqrt(2))^m)(sqrt(2)/4).

Or you can write a recurrence relation.  That means that you have one
solution (corresponding to m=1) with

  x = 3, y = 2

(so what do n and k equal?) and then you can find progressively larger
solutions by changing x and y to

  3x + 4y   and   2x + 3y,

respectively (which corresponds to increasing m by 1).  Repeating this
will eventually get to every solution.  (Of course, there are
infinitely many solutions.)

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/