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

Question

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.

Answer 1

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\;.$$

Answer 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 $.