# Prove by induction on $n$ that every product of $n$ sums of two squares is a sum of two squares

Use induction to show that for any natural number $n\ge 1$, given pairs $(a_1,b_1),(a_2,b_2),\ldots,(a_n,b_n)$ of integer numbers, there exist integer numbers $c$ and $d$ such that $(a_1^2+b_1^2)(a_2^2+b_2^2)\cdots(a_n^2+b_n^2)=c^2+d^2$.

At first I tried expressing it like the Pythagorean Theorem, but that doesn't work for all squares. I checked out the base case, and I'm on the inductive step. I can't seem to figure it out. I'm only one month into my Discrete class, so the answer shouldn't be anything terribly complicated. I would appreciate any and all help.

• Don't make us follow links. – Doug M Oct 4 '16 at 23:30
• Hint?: $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$ – CIJ Oct 4 '16 at 23:30
• You can surely find a descriptive title. In fact, you should not out your problem in the title: only describe it. Also: please copy the problem of the question in the qu re action body: linking to ab image is a bad idea. – Mariano Suárez-Álvarez Oct 4 '16 at 23:31
• Sorry about that guys, I really did try to think of a descriptive title. I did not mean to make it vague and make anyone click on a link. – sgruggy Oct 4 '16 at 23:33
• @CarlosIsraelJrl I think I substitute P(n) for (c2+d2), then multiply this by the (a2+b2) made by P(n + 1), and show that this can also be written as a sum of squares? This actually makes a lot of sense to me. I think this is it. Thanks! – sgruggy Oct 4 '16 at 23:35

HINT: For your induction step you’re assuming that any product of $n$ sums of two squares is a sum of two squares. Then

$$(a_1^2+b_1^2)(a_2^2+b_2^2)\ldots(a_n^2+b_n^2)(a_{n+1}^2+b_{n+1}^2)=(c^2+d^2)(a_{n+1}^2+b_{n+1}^2)$$

for some integers $c$ and $d$ by the induction hypothesis, and you’ve reduced the problem to the case $n=2$. Now use the hint provided by Carlos Israel Jrl in the comments:

$$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\;.$$

More generally, the product of terms of the form $x^2-dy^2$ is of that form.

The key step in the induction is this:

$\begin{array}\\ (u^2-dv^2)(x^2-dy^2) &=u^2x^2-du^2y^2-dv^2x^2+d^2v^2y^2\\ &=u^2x^2+d^2v^2y^2-d(u^2y^2+v^2x^2)\\ &=u^2x^2-2duvxy+d^2v^2y^2-d(u^2y^2-2uvxy+v^2x^2)\\ &=(ux-dvy)^2-d(uy-vx)^2\\ \end{array}$

Setting $d=-1$, we get $(u^2+v^2)(x^2+y^2) =(ux+vy)^2+(uy-vx)^2$.