0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Don't make us follow links. $\endgroup$ – Doug M Oct 4 '16 at 23:30
  • 2
    $\begingroup$ Hint?: $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$ $\endgroup$ – CIJ Oct 4 '16 at 23:30
  • $\begingroup$ 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. $\endgroup$ – Mariano Suárez-Álvarez Oct 4 '16 at 23:31
  • $\begingroup$ 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. $\endgroup$ – sgruggy Oct 4 '16 at 23:33
  • 1
    $\begingroup$ @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! $\endgroup$ – sgruggy Oct 4 '16 at 23:35
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.