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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum