0

I have encountered into very nice problem.

Prove that for any positive integer $n\geqslant 2$ there is a positive integer $m$ that can be written simultaneously as a sum of $2, \ 3, \dots, \ n$ squares of nonzero integers.

My solution:

I have tried to do it via math induction.

Firstly, for $n=2$ we can take $m=2=1^2+1^2$

Also for $n=3$ there is $m=17=4^2+1^2=2^2+2^2+3^2$ (this is not mandatory, i just wanted to make sure that such number indeed exists).

Suppose for $n$ there is number $m=m(n)$ with desired properties.

Then we should prove it for $n+1$, i.e. we have to find number $M$ such that $M$ can be written as a sum of $2,3,\dots,n,n+1$ squares of nonzero integers.

It's not difficult to verify that for example if we take $M=m+1$ or $M=4m+1$ or in general $M=k^2m+1$ then $M$ is indeed sum of $3,4,..,n,n+1$ squares of nonzero integers (in each case). But I am not able to show that at least one of them cam be written also as a sum of two squares. This is a hurdle which I cannot overcome.

Maybe you have any suggestion?

It would be great.

RFZ
  • 16,814
  • Related: https://math.stackexchange.com/questions/2537002/number-which-is-simultaneously-sum-of-2-and-3-squares – Ethan Bolker Nov 26 '17 at 14:40
  • @EthanBolker, Yes, this topic was created by me. However, I cannot the relation between them. :( – RFZ Nov 26 '17 at 15:10

2 Answers2

3

$$3^2+4^2=5^2$$ $$5^2+12^2=13^2$$ $$13^2+84^2=85^2$$ $$85^2+3612^2=3613^2$$ I can keep going as far as I like... $$3613^2=3612^2+85^2=3612^2+84^2+13^2=3612^2+84^2+12^2+5^2=3612^2+84^2+12^2+4^2+3^2$$ etc.

Angina Seng
  • 158,341
  • I know that the general formula for Pythagorean triples are $(a,b,c)=(x^2-y^2,2xy,x^2+y^2)$ such that $a^2+b^2=c^2$. But how to generate your sequence of equations? – RFZ Nov 26 '17 at 17:15
  • @RFZ I used $(m+1)^2-m^2=2m+1$. – Angina Seng Nov 26 '17 at 17:19
  • What is $m$ in your expression? – RFZ Nov 26 '17 at 17:20
  • @RFZ In, say the last entry, it is the $m$ which solves $2m+1=85^2$. – Angina Seng Nov 26 '17 at 17:21
  • But I would like to transfer your solution to induction but i guess its hard or not? – RFZ Nov 26 '17 at 17:22
  • @RFZ It's quite easy to prove by induction. If you have an odd number $a$ which is the sum of $1$, $2,\ldots,k$ integer squares, then it's easy to write down an odd number $b$ which is the sum of $1$, $2,\ldots,k+1$ integer squares. – Angina Seng Nov 26 '17 at 17:27
  • I have given here full proof via induction. Please take a look. https://math.stackexchange.com/questions/2539241/induction-proof-of-contest-math-problem – RFZ Nov 27 '17 at 08:16
2

One approach is to start with $a=b^2+c^2$ and find a Pythagorean triple like $5^2=4^2+3^2$. Then you can write $$25a=(5b)^2+(5c)^2\\=3^2b^2+4^2b^2+(5c)^2\\=3^2b^2+4^2b^2+3^2c^2+4^2c^2$$ and we are up to $4$. Now multiply again by $25$ (or any other Pythagorean hypotenuse square) and expand the terms again and you get up to $8$.
$$625a=3^25^2b^2+4^25^2b^2+3^25^2c^2+4^25^2c^2$$

You can expand each of the $5^2$s on the right to add one more term. Keep going until you are tired.

Ross Millikan
  • 374,822
  • Your post is very interesting but how to do that by induction? I mean how to write your solution in induction – RFZ Nov 26 '17 at 17:17
  • For an informal inductive proof, we are done. I have shown how to get an expression with any number of terms that is a power of $2$ and how to get all the numbers up to the next power of $2$. You alternate between multiplying by $25$ and then replace each $5^2$ in turn by $3^2+4^2$. – Ross Millikan Nov 26 '17 at 20:23
  • If I wanted to be more formal about it, I would use a constructive proof. If you want $k$ terms on the right, find $m$ so that $2^{m-1}\lt k \le 2^m$, then write $2\cdot 25^m=(3^2+4^2)^m+(3^2+4^2)^m$ and show you can choose how many terms on the right to expand to get any number in the range. – Ross Millikan Nov 26 '17 at 20:27