This question already has an answer here:

While playing with sums $S_n = 1+\cdots+n$ of integers, I have just come across some "mathematical magic" I have no explanation and no proof for.

Maybe you can give me some comments on this:

I had the computer calculating which Sn are squares, and it came up with the following list:


row $N$ sum($1+\cdots+N$) M (square root of sum)

r=1 N=1 sum=1 M=1

r=2 N=8 sum=36 M=6

r=3 N=49 sum=1225 M=35

r=4 N=288 sum=41616 M=204

r=5 N=1681 sum=1413721 M=1189

r=6 N=9800 sum=48024900 M=6930

Of course we have $1+\cdots+N = \frac{N(N+1)}{2}$, but this gives no indication for which N the sum $1+\cdots+N$ is a square.

Can you guess how in this table we can calculate the entries in row 2 from the entries in row 1? Or the entries in row 3 from the entries in row 2? Or the entries in row 4 from the entries in row 3? Or the entries in row 5 from the entries in row 4?

I looked at the above table and made some strange observations:

  1. The value of the next M can be easily calculated from the previous entries: Take the M from the previous row, multiply by 6 and subtract the M from two rows higher up. $M(r) = 6*M(r-1)–M(r-2)$ How is this possible?

    The S(r) we calculate as $S(r) = M(r)^2$. Note that we do not know whether this newly constructed number $S_r$ is in fact of the type $1+\cdots+k$ for some $k$.

  2. The value of the next N can be calculated as N(r) = Floor($M(r)*\sqrt 2$), where Floor means “rounding down to the next lower integer“. Somewhat surprising, $S(r)$ is the sum $1+\cdots+N(r)$ !

  3. It looks as if outside the entries in the above table there are no other cases. With other words, the method $M(r) = 6*M(r-1)–M(r-2)$ seems to generate ALL solutions n where the sum $1+\cdots+n$ is a square.


Is there a proof for any of the three observations? Do observations 1 and 2 really work for the infinite number of rows in this table? Is there an infinite number of rows in the first place?

Puzzled, Karl


marked as duplicate by Ross Millikan, user7530, Alex Wertheim, hardmath, user63181 Dec 23 '13 at 7:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ math.stackexchange.com/questions/76040/… $\endgroup$ – MJD Dec 23 '13 at 3:04
  • $\begingroup$ math.stackexchange.com/questions/394858/… $\endgroup$ – MJD Dec 23 '13 at 3:26
  • $\begingroup$ $N(r)$ has an explicit formula. $$N(r) = \frac{(3+2\sqrt{2})^r + (3-2\sqrt{2})^r - 2}{4} = \left\lfloor \frac{ (3+2\sqrt{2})^r}{4}\right\rfloor$$ Too see this, either follow the answer in MJD's first link or prove it yourself by induction using the construction in Will Jagy's answer. $\endgroup$ – achille hui Dec 23 '13 at 5:37

I see. Nobody answered this the way I would have... Taking $u = 2 n+1,$ we are solving $$ u^2 - 8 m^2 = 1. $$ A beginning solution is $(3,1).$ Given a solution $(u,m),$ we get a new one $$ (3 u + 8 m, u + 3 m). $$ Then $n = (u-1)/2$ for each pair.

So, with $n^2 + n = 2 m^2$ and $u = 2 n + 1,$ we get triples $$ (n,u,m) $$ $$ (1,3,1) $$ $$ (8,17,6) $$ $$ (49,99,35) $$ $$ (288,577,204) $$ $$ (1681,3363,1189) $$ $$ (9800,19601,6930) $$ $$ (57121,114243,40391) $$ $$ (332928,665857,235416) $$ $$ (1940449,3880899,1372105), $$

With my letters, each is a similar sequence, let us use $r$ for "row," $$ m_1 = 1, m_2 = 6, \; \; m_{r+2} = 6m_{r+1} - m_r, $$ $$ u_1 = 3, u_2 = 17, \; \; u_{r+2} = 6u_{r+1} - u_r, $$ $$ n_1 = 1, n_2 = 8, \; \; n_{r+2} = 6n_{r+1} - n_r + 2. $$


This problem shows up often when working with Pythagorean triangles with consecutive sides. (3,4,5), (20,21,29) etc.

I will answer half the question and the other half is similar. $$\frac{N (N+1)}{2}$$ will be perfect square only when $N$ is square and $(N+1)/2$ is a square or $N/2$ is a square and $N+1$ is a square (this is true since $N$ and $N+1$ are co-prime).

Now consider the first case. $N$ is necessarily odd; so $$ N = (2k+1)^2 = 4k^2+4k+1$$ and $$ \frac{N+1}{2} = 2k^2 + 2k + 1 = k^2 + (k+1)^2$$ Hence we need $$ k^2 + (k+1)^2 = m^2$$ The solution is just Pythagorean triangle with consecutive sides. Refer to any elementary number theory book for finding these.

  • $\begingroup$ Let me add to my answer. Pythagorean triangles with consecutive sides are almost 45, 45, 90 triangle so that the ratio of side to hypotenuse is almost $\sqrt{2}$. In fact the sides of the triangles are obtained by the best approximation to $\sqrt{2}$. Thus the connection between $\sqrt{2}$ and the answer. Hope this answers one of your questions. $\endgroup$ – user44197 Dec 23 '13 at 5:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.