Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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.)

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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search