# Find $n$ for which $\frac{n(n+1)}{2}$ is perfect square

Prove there is an infinite amount of natural numbers for which $\displaystyle \frac{n(n+1)}{2}$ is a perfect square.

-
What did you try ? –  Belgi Jan 4 '13 at 23:22
See also this question –  Andrew Uzzell Jan 8 '13 at 18:49

Equations such as these fall under the category of what are known as Pell's equation. A more general class of equations are called Diophantine equation. Diophantine equation is a polynomial equation in two or more variables, where the variables are allowed to take only integer values. For instance, finding the integer solutions for $3x+4y = 5 \,\,\,\,\, (\star)$ is a classic example of a linear Diophantine equation in two variables. The general solution to the above equation $(\star)$ is given by $(3+4n,-1-3n)$ where $n$ is any integer.

In general though, the degree of the Diophantine equation can be arbitrary and the number of variables can also be arbitrary in number. Pell's equation form a special class of Diophantine equation. It is quadratic equation in two variables of a specified type as shown below. $$x^2 - Ny^2 = 1$$ where $N$ is a non-square integer i.e. $N$ can be say $2,3,5,6,7,8,10,11,12,13,14,15,17,\ldots$. This equation was first studied by Brahmagupta, who lived around $6^{th}$ century A.D. We will in-fact use his method named "Chakravala method" to solve the original problem. The sanskrit name "Chakravala" stands for "cyclic". The "Chakravala method" hinges on the following identity $$(x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2 ) = (x_1x_2 + Ny_1 y_2)^2 - N(x_1y_2 + x_2y_1)^2.$$ The name "Chakravala" is due to the fact that we start with two numbers of the form $x^2-Ny^2$ and multiply it out to get back another number of the form $x^2 - Ny^2$. Hence, if $(x_1,y_1)$ and $(x_2,y_2)$ satisfy $x^2 - Ny^2 = 1$ i.e. if we have $x_1^2 - Ny_1^2 = 1$ and $x_2^2 - Ny_2^2 = 1$, then multiplying the two out and rearranging, we get that $$(x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2 ) = (x_1x_2 + Ny_1 y_2)^2 - N(x_1y_2 + x_2y_1)^2 = 1$$ This gives us a way to generate more solutions since $(x_1x_2 + Ny_1 y_2,x_1y_2 + x_2y_1)$ now satisfies $x^2 - Ny^2$. In fact, if we know that $(x_1,y_1)$ satisfy $x_1^2 - Ny_1^2 = 1$, then $$(x_1^2 - Ny_1^2)(x_1^2 - Ny_1^2) = 1 \implies (x_1^2 + Ny_1^2)^2 - N(2x_1y_1)^2 = 1$$In fact, more can be said. If we choose $(x_1,y_1)$ appropriately satisfying $x_1^2 - Ny_1^2 =1$, then all the solutions can be obtained as $$\left( \dfrac{\left(x_1 + \sqrt{N} y_1 \right)^n+\left( x_1 - \sqrt{N} y_1 \right)^n}{2} , \dfrac{\left(x_1 + \sqrt{N} y_1 \right)^n-\left( x_1 - \sqrt{N} y_1 \right)^n}{2\sqrt{N}} \right)$$ where $n$ is any positive integer. Note that $n=1$ gives us the original solution $(x_1,y_1)$. Let use see this in action.

Example:

Find all positive integer solutions for $x^2 - 2y^2 =1$. The reason we choose this example is that it is related to our original problem. First note that $(3,2)$ satisfies this problem since $3^2 -2 \times 2^2 = 1$. This will be the generator now. (This generator infact generates all positive integer solutions.) So now lets see how we generate solutions. We have \begin{align*} 3^2 - 2 \times 2^2 & = 1\\ (3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) & = 1\\ \end{align*} Now lets square both sides and proceed. \begin{align*} (3+ 2 \sqrt{2})^2 (3 - 2 \sqrt{2})^2 & = 1\\ (9 + 8 + 12 \sqrt{2}) (9 + 8 - 12 \sqrt{2}) & = 1\\ (17 + 12\sqrt{2}) (17 - 12\sqrt{2}) & = 1\\ 17^2 - 2 \times 12^2 & = 1 \end{align*} Hence, now we find that $(17,12)$ satisfies the equation $x^2 -2y^2 = 1$. Now lets find one more solution based on the same method and the general idea should be clear. As before, we have $(3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) =1$. Now lets cube both sides and proceed. $$(3+ 2 \sqrt{2})^3 (3 - 2 \sqrt{2})^3 = 1^3$$ $$(3^3 + 3 \times 3^2 \times 2 \sqrt{2} + 3 \times 3 \times (2 \sqrt{2})^2 + (2 \sqrt{2})^3) (3^3 - 3 \times 3^2 \times 2 \sqrt{2} + 3 \times 3 \times (2 \sqrt{2})^2 - (2 \sqrt{2})^3) = 1$$ $$(27 + 54 \sqrt{2} + 72 + 16 \sqrt{2}) (27 - 54 \sqrt{2} + 72 - 16 \sqrt{2}) = 1$$ $$(99 + 70 \sqrt{2}) (99 - 70 \sqrt{2}) = 1$$ $$99^2 - 2 \times 70^2 = 1$$ Hence, in general, we raise the equation $(3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) =1$ to the $n^{th}$ power on both sides to get the general solution. The general solution can be compactly written as $$(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^n+\left( 3 - 2\sqrt{2} \right)^n}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^n-\left( 3 - 2\sqrt{2} \right)^n}{2\sqrt{2}} \right)$$ where $n$ is any positive integer.

$n=1$ gives us $(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^1+\left( 3 - 2\sqrt{2} \right)^1}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^1-\left( 3 - 2\sqrt{2} \right)^1}{2\sqrt{2}} \right) = \left( 3,2\right)$.

$n=2$ gives us $(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^2+\left( 3 - 2\sqrt{2} \right)^2}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^2-\left( 3 - 2\sqrt{2} \right)^2}{2\sqrt{2}} \right) = \left( 17,12\right)$.

$n=3$ gives us $(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^3+\left( 3 - 2\sqrt{2} \right)^3}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^3-\left( 3 - 2\sqrt{2} \right)^3}{2\sqrt{2}} \right) = \left( 99,70\right)$.

$n=4$ gives us $(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^4+\left( 3 - 2\sqrt{2} \right)^4}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^4-\left( 3 - 2\sqrt{2} \right)^4}{2\sqrt{2}} \right) = \left( 577, 408\right)$.

$n=5$ gives us $(x,y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^5+\left( 3 - 2\sqrt{2} \right)^5}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^5-\left( 3 - 2\sqrt{2} \right)^5}{2\sqrt{2}} \right) = \left( 3363, 2378\right)$. and so on...

Getting back to the original problem:

Let us now see how this is related to our original problem. The original problem led us to the equation $(n^2 + n) -2 x^2 = 0$. Multiplying by $4$ gives us $(4n^2 + 4n) - 8x^2 = 0$. Adding $1$ gives us $$(4n^2 + 4n + 1) - 2(2x)^2 = 1 \implies (2n+1)^2 - 2(2x)^2 = 1$$ Calling $(2n+1)$ as $X$ and $2x$ as $Y$, we get that $X^2 - 2Y^2 = 1$. This was precisely the problem we solved in the above paragraph. Hence, we can enlist all the solutions.

-
Brahmagupta lived around the 6th century AD, not 6 AD. Otherwise cool, +1. :-) –  ShreevatsaR Jan 8 '13 at 10:34
@ShreevatsaR Thanks. Have corrected it. –  user17762 Jan 8 '13 at 18:31

Rewrite as $4n^2+4n=8z^2$, then as $(2n+1)^2-8z^2=1$.

So we want to show that the Pell Equation $x^2-2y^2=1$ has infinitely many solutions with $n$ odd and $y$ even. But in fact all solutions have $x$ odd and $y$ even. This is easy to show, since the square of an odd number is congruent to $1$ modulo $8$.

The Pell equation $x^2-2y^2=1$ has fundamental solution $x=3$, $y=2$. By direct substitution, one can verify that if $(a,b)$ is a solution, then $(3a+4b,2a+3b)$ is a solution.

-
If you find two numbers $x,y$, such that $x^2-2y^2=\pm 1$, then $n=xy$ will work. Then you can prove that given a solution $(x,y)$, then $(x+2y,x+y)$ will be another solution. $(1,0)$ gets you started.