# Russelle’s Perfect Square

Our featured problem today is from one of the Philippines Representatives in 2011 International Math Olympiad , Russelle Guadalupe. He is currently studying at the University of the Phillipines – Diliman, taking up BS Mathematics.  He also won several championships in local math challenges. Here are some of the of his achievements in his Mathematics career.

2009 MTAP Math Challenge Individual Cat B( 2nd Place Sectoral, 8th Place Regional )

2009 MTAP Math Challenge Team Orals Cat B ( 3rd Place Sectoral, 2nd Place Regional )

2010 MTAP Math Challenge Individual Cat B( 1st Place Sectoral, 7th Place Regional )

2010 MTAP Math Challenge Team Orals Cat B ( 3rd Place Sectoral )

2011 MTAP Math Challenge Individual ( 2nd Place Sectoral, 4th Place Regional )

2011 MTAP Math Challenge Team Orals ( 1st Place Sectoral, 2nd Place Regional )

13th Phil Math Olympiad Area Stage ( 3rd Place )

13th Phil Math Olympiad Nat’l Stage ( Finalist )

2011 International Math Olympiad ( Participant)

2012 MTAP Math Challenge Individual ( 1st Place Sectoral, 1st Place Regional )

2012 MTAP Math Challenge Team Orals ( 1st Place Sectoral )

2012 1st Raffles Invitational Math Olympiad (RIMO) ( Bronze Medal )

2011 – Canadian Mathematics Contest Senior Category ( Medalist )

2012 – Euclid Mathematics Contest ( Top 25% of all contestants )

2011 – 6th Philippine Sudoku Super Challenge Elims ( Finalist )

2011 – Sharp MTG Math Trail and Problem Solving Competition ( 3rd Runner Up )

2013 – International Regions Math League ( Top Scorer )

Now, here is a breathtaking problem from Russelle himself. Hope you will learn from this.

Problem:

Let $f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2$. Determine the sum of all positive integers $n\leq 1000$ for which $f(n)$ is a perfect square.

( 2014 EMC Online Test Problem 14)

Solution:

First, we need to find a closed-form expression for $f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2$ by summing each term involving $j$ and treating terms involving $i$ as a constant. Thus, we have $f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2=\sum_{i=1}^n\sum_{j=1}^{n} (i^2-2ij+j^2)=\sum_{i=1}^n[i^2\sum_{j=1}^n 1-2i\sum_{j=1}^n j+\sum_{j=1}^n j^2]$ $=\sum_{i=1}^n[ni^2-2i\cdot \displaystyle\frac{n(n+1)}{2}+\displaystyle\frac{n(n+1)(2n+1)}{6}$ $=n\sum_{i=1}^n i^2-n(n+1)\sum_{i=1}^n i+\displaystyle\frac{n(n+1)(2n+1)}{6}\sum_{i=1}^n 1$ $=n\cdot \displaystyle\frac{n(n+1)(2n+1)}{6}-n(n+1)\cdot \displaystyle\frac{n(n+1)}{2}+\displaystyle\frac{n(n+1)(2n+1)}{6}\cdot n$ $=n^2(n+1)[ \displaystyle\frac{2n+1}{3}-\displaystyle\frac{n+1}{2}]$ $=\displaystyle\frac{n^2(n^2-1)}{6}$

Thus, $f(n)=\displaystyle\frac{n^2(n^2-1)}{6}$. We then find all positive integers $N$ such that $f(N)=t^2$ for some nonnegative integers $t$. This is equivalent to $N^2(N^2-1)=6t^2$ or $(2N^2-1)^2=24t^2+1$. Letting $x=2N^2-1$. We have $x^2-24t^2=1$, a Pell’s equation. The general solution for this equation is given by $x_k=\displaystyle\frac{(x_1+t_1\sqrt{24})^k+(x_1-t_1\sqrt{24})^k}{2}$, $t_k=\displaystyle\frac{(x_1+t_1\sqrt{24})^k-(x_1-t_1\sqrt{24})^k}{2\sqrt{24}}$

For all integers $k\geq 0$, where $(x_1,t_1)$ is the initial solution. Clearly, by testing values with $t_1>0$, we have $(x_1,t_1)=(5,1)$. Thus, we can then make a sequence $\{N_k\}_{k\geq 0}$ of values of $N$ based from the solutions of the given Pell’s equation. Note that $N_k^2=\displaystyle\frac{x_k+1}{2}=\displaystyle\frac{1}{2}[\displaystyle\frac{(5+\sqrt{24})^k+(5-\sqrt{24})^k}{2}+1]$ $=\displaystyle\frac{1}{2}[\displaystyle\frac{(5+2\sqrt{6})^k+(5-2\sqrt{6})^k}{2}+1]$ $=\displaystyle\frac{1}{2}[\displaystyle\frac{(\sqrt{3}+\sqrt{2})^{2k}+(\sqrt{3}-\sqrt{2})^{2k}}{2}+1]$ $=\displaystyle\frac{(\sqrt{3}+\sqrt{2})^{2k}+2+(\sqrt{3}-\sqrt{2})^{2k}}{4}$ $=[\displaystyle\frac{(\sqrt{3}+\sqrt{2})^k+(\sqrt{3}-\sqrt{2})^k}{2}]^2$

Thus, we have $N_k=\displaystyle\frac{(\sqrt{3}+\sqrt{2})^k+(\sqrt{3}-\sqrt{2})^k}{2}$. Since $(\sqrt{3}+\sqrt{2})^k=\sum_{p=0}^k {k\choose p}3^{\frac{p}{2}}\cdot 2^{\frac{k-p}{2}}$ $(\sqrt{3}-\sqrt{2})^k=\sum_{p=0}^k {k\choose p}3^{\frac{p}{2}}\cdot 2^{\frac{k-p}{2}}(-1)^p$

we have $N_k=\sum_{m=0}^{\lfloor \displaystyle\frac{k}{2}\rfloor} {k\choose 2m}3^m\cdot 2^{\frac{k}{2}-m}$,  which follows that $N_k$  is an integer when $k$  is even. Thus, it suffices to check the values of $N_k$  for $k\leq \log_{\sqrt{3}+\sqrt{2}} 200<7$ (since $N_k\leq 1000$) and $\sqrt{3}+\sqrt{2}>1.7+1.4=3.1>3$  implies $(\sqrt{3}+\sqrt{2})^7>2187>2000$.) Thus, $k\in \{0,2,6\}$, so by brute force calculation we get $N_0=1,N_2=5,N_4=49$ and $N_6=485$. Therefore, the sum of all integers $N\leq 1000$ such that $f(N)$ is a perfect square is $1+5+49+485=\boxed{540}$.