2
$\begingroup$

Prove that for every $n\in\mathbb{N}$ there are infinitely many ways to represent $n$ as $$ n=*1^2*2^2*\dots*k^2, $$ where $k\in\mathbb{Z}$ and $*\in\{+,-\}$.

On my paper, this problem is marked as "Erdos-Suranyi", but I could find anything about it on Google.

  • 1
    RE: "On my paper".. is this a `(homework)` question?2012-03-12
  • 1
    There's no need to use `\large` here. Also, I edited your title to make it self-contained; please check that I didn't change your meaning.2012-03-12
  • 0
    In any case, you just need to find *one* way to represent $n$ as a sum and difference of squares, and then you can always add $a^2+b^2-c^2$ for any Pythagorean triple $(a,b,c)$ to get infinitely many different representations.2012-03-12
  • 0
    It is unclear whether one can add or subtract *any* squares, or if *every* square from $1^2$ through some $k^2$ must appear in the expression.2012-03-12
  • 0
    @J.D. It's not homework, it's on the paper for preparing for national competition, we couldn't manage to do it on class few weeks ago so it was left undone on my paper.2012-03-12
  • 0
    I suspect that notation simply means that the problem (or the result) can be found in *Topics in the Theory of Numbers*, by Erdős and Surányi.2012-03-12

1 Answers 1

4

The classic solution to show existence of one solution is to use the identity

$$ (n+3)^2 - (n+2)^2 - (n+1)^2 + n^2 = 4$$

and the fact that $1,2,3,4$ have a representation:

$$1 = + 1^2$$ $$2 = - 1^2 - 2^2 - 3^2 + 4^2$$ $$3 = -1^2 + 2^2$$ $$4 = -1^2 - 2^2 + 3^2$$

To get one representation of $4m+r$, we inductively get one representation for $4(m-1) + r$, and use the above identity.

Now, as Andre pointed out, given one representation we can extend that to infinitely many representations by writing $0+0+0 \dots$ as $(4 - 4) + (4-4) + (4-4) \dots$ and using the above identity multiple times.