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.

russelle

 

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}.

Dan

Dan

Blogger and a Math enthusiast. Has no interest in Mathematics until MMC came. Aside from doing math, he also loves to travel and watch movies.
Dan

Latest posts by Dan (see all)

You may also like...

6 Responses

  1. Darrin says:

    Fantastic items from you, man. I have be aware your stuff prior to and you are simply too great. I really like what you have obtained right here, really like what you are stating and the best way in which you assert it. You make it entertaining and you still care for to keep it sensible. I cant wait to learn far more from you. This is actually a great site.

  2. There’s noticeably a bundle to learn about this. I assume you made sure nice points in features also.

  3. Excellent beat ! I wish to apprentice while you amend your website, how can i subscribe for a weblog site? The account aided me a appropriate deal. I have been tiny bit acquainted of this your broadcast offered vibrant transparent concept

  4. Wilson Ruben says:

    Thank you of this blog. That’s all I’m able to say. You undoubtedly have made this web web site into an item thats attention opening in addition to critical. You certainly know a fantastic deal of about the niche, youve covered a multitude of bases. Fantastic stuff from this the main internet. All more than again, thank you for the blog.

  5. Thank you of this blog. That’s all I’m able to say. You undoubtedly have made this web web site into an item thats attention opening in addition to critical. You certainly know a fantastic deal of about the niche, youve covered a multitude of bases. Fantastic stuff from this the main internet. All more than again, thank you for the blog.

  6. Thank you of this blog. That’s all I’m able to say. You undoubtedly have made this web web site into an item thats attention opening in addition to critical. You certainly know a fantastic deal of about the niche, youve covered a multitude of bases. Fantastic stuff from this the main internet. All more than again, thank you for the blog.

Leave a Reply

Your email address will not be published. Required fields are marked *