# Use induction to prove a product of sums of squares is a sum of squares

For any natural number $n\ge 1$, given pairs $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ of integer numbers, there exist integer number $c$ and $d$ such that

$$\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$$

My initial approach is

Base Case: $(a_1^2+b_1^2) = a_1^2+b_1^2$ which is true. (Although it is trivial)

Prove the statement is true when $n=2$: We have $$(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$$ (Thanks André Nicolas for pointing it out)

So if $a,b,c,d$ are integers, $ac,bd,ad,bc$ are all integers and integers are closed under addition and subtraction. Hence $(ac-bd),(ad+bc)$ are integers.

Inductive Hypothesis: $\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$ is true

Inductive Step: $$\prod_{i=1}^{n+1}(a_i^2+b_i^2) = \prod_{i=1}^{n}(a_i^2+b_i^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2)$$ Where $c$ and $d$ are integers.

But when we apply $n=2$, we have $(c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (e^2 + f^2)$ where $e$ and $f$ are integers.

Hence, by the principle of induction, the statement we needed to prove is true.

-
And how exactly do you go from the $n=1$ case to the $n=2$ case using this inductive argument? You still need to show the $n=2$ case. In fact, it's best not to say that the $n=2$ case is a "special case of the inductive hypothesis", since you are not assuming the result holds for any product with fewer than $n+1$ factors, you are only assuming it is true for exactly $n$ factors. –  Arturo Magidin Dec 7 '11 at 5:43
@ArturoMagidin Thanks for pointing that out. But then how can I approach this problem. –  geraldgreen Dec 7 '11 at 5:52
@John.Mathew Hint: Use complex multiplication $(a_1+b_1i)(a_2+b_2i)=\cdots$, and therefore $\cdots$ –  Jyrki Lahtonen Dec 7 '11 at 6:01
@John.Mathew: You are on an appropriate track, you just need to be a lot more careful with what induction is and how it works. –  Arturo Magidin Dec 7 '11 at 6:10
@ArturoMagidin Thanks a lot for your help. –  geraldgreen Dec 7 '11 at 6:35

Let me raise a couple of points:

1. You should prove the basis of the induction (the $n=1$ case); even if it is obvious, it should be mentioned.

2. The induction hypothesis that you put forth is just "If the result holds for $n$, then it holds for $n+1$." You are not assuming that the result holds for all values of $n$, just for a single, though unspecified, value. For the inductive step to be valid, the proof must be valid for any particular value of $n$ that you may use. That is: you do not have "general cases" and "specific cases" of the induction hypothesis, you have a single, fixed, induction hypothesis: that the result holds for a particular, fixed (though unspecified) $n$. You are trying to prove a universal statement ("For all natural numbers $n$, if the result holds for $n$ then it holds for $n+1$") by taking an arbitrary $n$.

3. It is possible to do the inductive step by assuming that the result holds for all values of $k$ smaller than $n$; this is sometimes called "strong" or "transfinite induction." There are some subtle differences between strong induction as applied to the natural numbers and regular "one-step-at-a-time" induction: see for example this post.

4. Even so, inductive argument must be such that it must hold for all values of $n$. Your argument does not let you go from $P(1)$ to $P(2)$.

A particular "fake proof" that I like seems particularly appropriate here. Consider the following statement:

In any finite nonempty group of people, if at least one has blue eyes, then they all have blue eyes.

Here's a "proof" by induction: let $n$ be the number of people in the group. We prove the statement by induction.

Base: $n=1$. Then there is only one person, and if that person has blue eyes, then all persons have blue eyes.

Induction hypothesis: In any group with $n$ people, if at least one has blue eyes, they all have blue eyes.

Inductive step: Take a group with $n+1$ people, $p_1,p_2,\ldots,p_n,p_{n+1}$, and assume that one of them has blue eyes. Without loss of generality, say it is $p_1$. So we have the set: $$\{ {\color{blue}p_1}, p_2,\ldots,p_n,p_{n+1}\}.$$ Consider the set of the first $n$ people: $\{{\color{blue}p_1},p_2,\ldots,p_n\}$. By the induction hypothesis, since one of them has blue eyes, they all have blue eyes: $$\{ {\color{blue}p_1}, {\color{blue}p_2},\ldots,{\color{blue}p_n}, p_{n+1}\}.$$ Now consider the set of the last $n$ people: $$\{{\color{blue}p_2},\ldots, {\color{blue}p_n}, p_{n+1}\}.$$ Since at least one has blue eyes, they all have blue eyes: $$\{{\color{blue}p_2},\ldots, {\color{blue}p_n}, {\color{blue}p_{n+1}}\}.$$ Putting it all together, we have: $$\{ {\color{blue}p_1}, {\color{blue}p_2},\ldots,{\color{blue}p_n}, {\color{blue}p_{n+1}}\}.$$ Hence, all have blue eyes. By induction, the statement is proven.

What is the mistake?

The mistake is that the inductive argument does not work when $n=1$. One needs to prove the fact that $P(1)\implies P(2)$ somehow, and this argument does not work. (In fact, this is the step that doesn't work, period, which is why the statement is false...)

So, your argument is incomplete, even if reworded appropriately, because (i) you are missing the base; and (ii) the inductive argument does not work for going from $n=1$ to $n=2$.

In fact, the base is trivial; the real sticking point is the $n=2$ case. If you know the $n=2$ case is true, then you can also use it to replace the problem step in your "induction argument" as given: delete the step where you claim the conclusion follows because it "is just a special case of the induction hypothesis" (which is an invalid argument as given), and replace it with "since the $n=2$ case is true, then..."

That means that, after adding that the $n=1$ case is immediate and fixing your inductive argument above:

If you can prove the $n=2$ case directly, then you'll be done.

So... try to prove the $n=2$ case. If the $n=2$ case works, then you can invoke the $n=2$ case in your inductive step (which would be fine) rather than make the mistake of talking about "special cases" of the inductive hypothesis.

-
@John.Mathew: The $n=2$ case, by itself, is not enough. But look at your inductive argument: if you know that the $n=2$ case is true, then you can use it in the final part of your proof of the inductive step to replace the defective "special case of the inductive hypothesis: argument. That is: the case $n=1$, the case $n=2$, and your argument (properly edited) will establish the result. –  Arturo Magidin Dec 7 '11 at 6:13
I have revised my work. Is this work more righteous? –  geraldgreen Dec 7 '11 at 6:20
@John.Mathew: Yes, except for one tiny nit-pick: "This is true since we have already proven it." Technically, the only thing "this" could refer to is the statement "[This] is the $n=2$ case." But that is not what you meant; rather, say "Applying the $n=2$ case, we have..." –  Arturo Magidin Dec 7 '11 at 6:26
Just for giggles, if all the $\gcd(a_i, b_i)=1,$ you can arrange (and prove that you can arrange) that $\gcd(c, d)=1.$ –  Will Jagy Dec 7 '11 at 6:29

The following identity is useful: $$(a^2+b^2)(x^2+y^2)=(ax\pm by)^2 + (ay \mp bx)^2.\qquad\qquad(\ast)$$ This identity is connected with the multiplication of complex numbers. Note that $$(a+ib)(x+iy)=ax-by+i(ay+bx).$$ The identity $(\ast)$ can be thought of as asserting that the product of the norms of $a+ib$ and $x+iy$, namely $\sqrt{(x^2+y^2)(a^2+b^2)}$, is equal to the norm of their product, namely $\sqrt{(ax-by)^2 +(ay+bx)^2}$.

-
Sometimes this is called Fibonacci's identity; sometimes it's called Brahmagupta's identity. See this URL: en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity –  Michael Hardy Dec 7 '11 at 20:19

This is like Polya's famous proof that all horses have the same color (the metaphor "horse of a different color" is perhaps less universally known than formally, so maybe that name for it doesn't work as well as it used to?).

It's trivial if there's only one horse: one horse---one color.

For $n+1$ horses called $1,2,3,4,\ldots,n,n+1$ look at the sets $\{1,2,3,\ldots,n\}$ with only $n$ horses, and $\{2,3,4,\ldots,n,n+1\}$, also with only $n$ horses. In any set of $n$ horses, they all have the same color, since that's the induction hypothesis. But those two sets overlap, so there's just one color among all $n+1$ horses.

Lots of proofs by induction are like this: Vacuously true if $n=1$; and the induction step is trivial, but the induction step doesn't work when $n=1$, and that one case---that it's true when $n=2$---is the really hard part.

-
Though in the products of sums of squares case the $n=2$ step may be harder than the other steps, but is not not "really hard" –  Henry Dec 12 '11 at 0:11
@Henry But if it had been a different proposition, it could have been. :-) It's the "substantial" part. –  Michael Hardy Dec 12 '11 at 4:44

Hint $\$ By induction, closure under binary products extends to closure under $\rm\:n$-ary products.

Theorem $\$ If $\rm\ S\subset \mathbb N\$ and $\rm\ s,s'\in S\ \Rightarrow s\:s'\in S\$ then $\rm\ s_1,\ldots,s_n \in S\ \Rightarrow\ s_1\cdots s_n\in S\:.$

Proof $\rm\,\ n=1\:$ clear. Assume as induction hypothesis: all products of $\rm\:n\:$ elements of $\rm\:S\:$ are in $\rm\:S.\:$ Now a length $\rm\:n\!+\!1\:$ product $\rm\:s_1\cdots\: s_{n}\:s'\$ factors as a length $\rm\:n\:$ product $\rm\:s = s_1\cdots\:s_n\:$ times $\rm\:s'.\:$ By induction $\rm\:s\in S.\:$ By hypothesis, $\rm\:s,s'\in S\ \Rightarrow\ s\:s'\in S,\:$ so proving the induction step. $\,$ QED

Your exercise is simply the special case where $\rm\:S = \mathbb N^2\! + \mathbb N^2,\:$ which has a binary product pulled back from the multiplicativity of norms of Gaussian integers (Brahmagupta–Fibonacci identity), yielding that such sums of squares are closed under multiplication.

-