discrete mathematics - 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.

Answer

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