25. A sequence $\left\{a_{n}\right\}$ of real numbers is defined by $a_{1}=1$ and for all integers $n \geq 1$,
$$
a_{n+1}=\frac{a_{n} \sqrt{n^{2}+n}}{\sqrt{n^{2}+n+2 a_{n}^{2}}} .
$$

Compute the sum of all positive integers $n<1000$ for which $a_{n}$ is a rational number.
25. 131
Solution. First, note that for $k \geq 1$,
$$
a_{k+1}^{2}=\frac{k(k+1) a_{k}^{2}}{k(k+1)+2 a_{k}^{2}} \Longleftrightarrow \frac{1}{a_{k+1}^{2}}-\frac{1}{a_{k}^{2}}=\frac{2}{k(k+1)}=\frac{2}{k}-\frac{2}{k+1}
$$
and summing the second equation from $k=1$ to $k=n-1$ with $n \geq 2$, we get
$$
\frac{1}{a_{n}^{2}}-\frac{1}{a_{1}^{2}}=\sum_{k=1}^{n-1}\left(\frac{1}{a_{k+1}^{2}}-\frac{1}{a_{k}^{2}}\right)=\sum_{k=1}^{n-1}\left(\frac{2}{k}-\frac{2}{k+1}\right)=2-\frac{2}{n} .
$$

Since $a_{1}=1$, we see that
$$
\frac{1}{a_{n}^{2}}=3-\frac{2}{n} \Longleftrightarrow a_{n}=\sqrt{\frac{n}{3 n-2}}
$$
for all integers $n \geq 1$ and we wish to find the sum of all positive integers $n<1000$ such that $\frac{n}{3 n-2}$ is a square of some rational number. To help us look for such integers $n$, we use the following lemma that provides integer solutions to the generalized Pell equation.
Lemma. ${ }^{1}$ Let $d$ be a squarefree positive integer, and let a and $b$ be positive integers such that $a^{2}-d b^{2}=1$. Set $u=a+b \sqrt{d}$. Then for each nonzero integer $n$, every solution of $x^{2}-d y^{2}=n$ is a power of $u$ times $x+y \sqrt{d}$ where $(x, y)$ is an integer solution of $x^{2}-d y^{2}=n$ with $|x| \leq \sqrt{|n|}(\sqrt{u}+1) / 2$ and $|y| \leq \sqrt{|n|}(\sqrt{u}+1) /(2 \sqrt{d})$.
We now let $g=\operatorname{gcd}(n, 3 n-2)$. Then $g \in\{1,2\}$ since $g \mid 3 n-(3 n-2)=2$. We now consider the following cases:
- Suppose $g=1$. Then $n=y^{2}$ and $3 n-2=x^{2}$ for some relatively prime positive integers $x$ and $y$. This leads us to the generalized Pell equation $x^{2}-3 y^{2}=-2$. Set $u=2+\sqrt{3}$, with $(2,1)$ being a solution of $x^{2}-3 y^{2}=1$ in positive integers. We now look for the positive integer solutions $(x, y)$ of $x^{2}-3 y^{2}=-2$ with $x \leq \sqrt{2}(\sqrt{u}+1) / 2 \approx 2.07$ and $y \leq \sqrt{2}(\sqrt{u}+1) /(2 \sqrt{3}) \approx 1.2$. We obtain $(x, y)=(1,1)$ as the only such integer solution, so by the above lemma, we see that all positive integer solutions $\left(x_{k}, y_{k}\right)$ of $x^{2}-3 y^{2}=-2$ are given by $x_{k}+y_{k} \sqrt{3}=(1+\sqrt{3})(2+\sqrt{3})^{k}$ for all integers $k \geq 0$. We now compute this product for small values of $k$ :
As $n<1000$, we require that $y_{k} \leq 31$, so the positive integer solutions $\left(x_{k}, y_{k}\right)$ of $x^{2}-3 y^{2}=$ -2 with $y_{k} \leq 31$ are $\left(x_{k}, y_{k}\right)=(1,1),(5,3),(19,11)$ (which indeed have relatively prime coordinates). These correspond to the values of $n: n=1,9,121$.
- Suppose $g=2$. Then $n=2 y^{2}$ and $3 n-2=2 x^{2}$ for some relatively prime positive integers $x$ and $y$. This leads us to the generalized Pell equation $x^{2}-3 y^{2}=-1$. Again, we set $u=2+\sqrt{3}$. We now look for the positive integer solutions $(x, y)$ of $x^{2}-3 y^{2}=-1$ with $x \leq(\sqrt{u}+1) / 2 \approx 1.47$ and $y \leq(\sqrt{u}+1) /(2 \sqrt{3}) \approx 0.85$. It turns out that there are no such solutions on these bounds, so by the above lemma, we conclude that $x^{2}-3 y^{2}=-1$ has no solutions in positive integers.

Hence, the only positive integers $n<1000$ for which $a_{n}$ is a rational number are $n=1,9,121$ and the sum is $1+9+121=131$.