# Prove: If each of $m_1,\dotsc,m_n$ can be written as sums of two squares, so can their product $m_1 \dotsm m_n$

The Problem

Prove: If each of $m_1,\dotsc,m_n$ can be written as sums of two squares, so can their product $m_1 \dotsm m_n.$ (Hint: Use induction.)

(I believe that $m_1\dots m_n$ represent composite numbers in this case...)

Some Background

This problem is actually the third part of a multistep problem. The previous step had us do the following:

Prove: If $m_1$ and $m_2$ can be written as sums of two squares, so can their product $m_1 m_2$.

To which I offered the following proof:

Proof.

Suppose $m_1$ and $m_2$ can be written as sums of two squares, where $m_1=a^2+b^2$ and $m_2=c^2+d^2$. Then the product $m_1m_2=(a^2+b^2)(c^2+d^2)$. Having just showed that $(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$, we have $m_1m_2=(ac-bd)^2+(ad+bc)^2$. Letting $j=ac-bd$ and $k=ad+bc$, we have $m_1m_2=j^2+k^2$, which is the sum of two squares. $\square$

(The part where I used $(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$ was proven in the very first step of this problem.)

My Questions

I feel that this question shouldn't be much more difficult than the previous step, but I am failing to see how to apply induction here, and thus have been struggling to see how I should even start the problem off. More specifically,

1. Does the previous step count as the base case for this step, with $n=2$? If not, what should my base case look like?
2. What exactly should my inductive step look like here?

As always, your help is very appreciated!

1. Sort of, the previous step acts as both a proof for the base case (with $n=2$) and as the basis for the inductive step.

2. You assume that "if each $m_1, \ldots, m_n$ can be written as a sum of two squares then so can their product". You want to show that this assumption implies "if each $m_1,\ldots,m_{n}, m_{n+1}$ can be written as a sum of two squares, then so can their product.".

This isn't as hard as it looks. You know that $m_1m_2\cdots m_n$can be written as a sum of squares by using your induction hypothesis. You also know that $m_{n+1}$ can be written as a sum of two squares.

So can $$\underbrace{m_1 m_2 \cdots m_n}_{\text{sum of 2 squares}} \cdot \underbrace{m_{n+1}}_{\text{sum of 2 squares}}$$ be written as a sum of two squares? (think back to the previous part now, consider $m_1\cdots m_n$ and $m_{n+1}$ as your two numbers).

You are right. "The previous step" covers the induction case, since we are dealing with two numbers $m_1,m_2$ over there.

For induction, consider $k+1$ numbers $m_1, ...,m_{k+1}$ that can be written as the sum of two squares.

In the inductive step, you can assume that the product of $m_1, m_2, \ldots,m_k$ can be written as a sum of two squares (since here we can assume that for all integers $< k+1$, the premise is true).

Now, all you need to do, is to apply step two (or the inductive case $k=2$), with the two numbers $m_1 ... m_k$ (the product) and the last number $m_{k+1}$. That tells you that their product, which is $m_1 ... m_{k+1}$, is writable as a sum of two squares, which was to be proved.

So you were right, nothing more than step $2$ is required for the proof of the third part.