# Homework Help: Proof by induction of the sum of 2 squares

1. Jun 2, 2012

### aporter1

1. The problem statement, all variables and given/known data

(a^2+b^2)(c^2+d^2)=(ac-bd)^2 +(ad+bc)^2 prove by induction that r=a1,a2,a3...an where the a's represent the sums of 2 squares. it itself is a sum of two squares. Check it with: 2=1^2+1^2, 5=1^2+2^2, 8=2^2+2^2, for r=160, r=1600, r=1300, r=625

2. Relevant equations

3. The attempt at a solution
i know i have to start with the base case where n=1 and then move to n=K and show true for n=k+1
but i am not sure how to set this up with the given equations

2. Jun 3, 2012

### ArcanaNoir

the r=a1,a2,a3..an is confusing. can you clarify?

3. Jun 3, 2012

### aporter1

the problem says, prove by induction that any integer r= a1,a2,a3...an, where all the a's are the sums of 2 squares, is itself a sum of two squares.

the a1,a2,a3...an looks like the one is set below the a along with the others

4. Jun 3, 2012

### SammyS

Staff Emeritus
Hello aporter1. Welcome to PF !

So, does a1,a2,a3...an refer to a string of integers?

5. Jun 3, 2012

### aporter1

yes i believe so

6. Jun 3, 2012

### HallsofIvy

Then what does "any integer r= a1,a2,a3...an" mean? A string of integers is not equal to an integer.

7. Jun 3, 2012

### aporter1

i attached the problem. Its a Jpeg file and it's questionn number 8. Maybe that will help everyone out.

File size:
24.3 KB
Views:
191
8. Jun 3, 2012

### SammyS

Staff Emeritus
The problem reads as follows. Note that there are no commas between the a's, so r is the product of these numbers (a's) each of which is the sum of two squares.
(8) From the algebraic formula $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\,,$ prove by induction that any integer $r=a_1a_2\dots a_n\,,$ where all the a's are sums of two squares, is itself a sum of two squares. Check it with: 2=12+12, 5=12+22, 8=22+22, for r=160, r=1600, r=1300, r=625. If possible, give several different representations of these numbers as sums of two squares.​

So, it looks like you need to first prove it for n=2, then assuming it's true for n = k, show that it's true for n = k+1 .

9. Jun 4, 2012

### aporter1

I know i have to show true for that but I am unsure how to set up the problem. Once I know how to set it up I'm sure I can do it.

10. Jun 4, 2012

### SammyS

Staff Emeritus
Well, for n=2 it's pretty straight forward. Simply use the given algebraic identity.

Then, suppose it's true for n=k, where k ≥ 2.
Define each of $a_1,a_2,\dots a_{k+1}$ appropriately. So you assume that the product $a_1a_2\dots a_k$ is also the sum of two squares.

What does that tell you about $\left(a_1a_2\dots a_k\right)a_{k+1}\ ?$

11. Jun 4, 2012

### aporter1

so i start by setting up the problem as:
now,
what? I'm stuck.

12. Jun 4, 2012

### SammyS

Staff Emeritus
To make a subscript, use the "Go Avanced" button at the bottom of the message box, then use the X2 icon you see at the top of the new message box.

For exponents, use the X2 icon.

*****************************************

There should be no addition sign in a1a2...an+an+1. It should be a1a2...anan+1, where all the ak's are multiplied together.

If you assume your conjecture holds for n, what can you say about the number a1a2...an ?

13. Jun 4, 2012

### aporter1

now we show true for n≥2, a1a2...2= what do i put on this side?

Then I show true for n=k

14. Jun 5, 2012

### dimension10

This is what I understand from the problem:

If x is a sum of squares and y = x, then prove that y is also a sum of squares.

I don't even see why you need to prove that.

15. Jun 5, 2012

### SammyS

Staff Emeritus
No, that's not what's to be proved.

If x is the sum of two squares, and y is the sum of two squares, then the product xy is also the sum of two squares.

That's the case for n=2. This follows directly from the algebraic identity $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\ .$

16. Jun 5, 2012

### dimension10

Oh..

17. Jun 5, 2012

### aporter1

so am i on the right track?

18. Jun 5, 2012

### SammyS

Staff Emeritus
To start, you should state what it is that you are proving.

In your proof, you need to define all the quantities to which you refer.

To begin with, you should prove the case, n=2. How are a, b, c, and d related to a1 and a2 ?

After you do the proof for n=2:
Assume that the statement is true for n = k, where k ≥ 2. From that, show that the statement is true for n = k+1 .

COMMENT: It may help to do the "Checking" first.
Check it with: 2=12+12, 5=12+22, 8=22+22, for r=160 .

How many ways can you express 160 as the sum of two squares?​

19. Jun 5, 2012

### aporter1

i'm not sure how they are related, that's what i'm confused on. I'm not sure how they are supposed to be set up together.

20. Jun 5, 2012

### SammyS

Staff Emeritus
Well, it's hard to do a proof, when you don't understand what it says, or understand the background it rests upon.

Below is my post *8. The inset portion is your problem copied verbatim from the JPEG image you posted.
O.K. Now, what does this mean? (Don't be insulted. It's not my intention to be talking down to you.)

The problem statement starts with an "algebraic formula". It's actually an identity.
$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\,.$​
Have you verified for yourself that this is truly an identity?

What this identity says is: Multiply two quantities together. (a2+b2), which is the sum of two squares, a2 and b2; times (c2+d2), which is the sum of two other squares, c2 and d2. The identity says that the resulting product is equal to (ac-bd)2+(ad+bc)2, which is the sum of two squares, (ac-bd)2 and (ad+bc)2.
(I really wish they hadn't used the variable name, a, in two different ways; here as a, later as ai in a different context.)​
Now, let's look at what's to be proved:

Prove (by induction):
Any integer, r, which may be expressed in the form, $r=a_1a_2\dots a_n\,,$ where each of the a's is the sum of two squares, is also the sum of two squares.

In other words, if an integer r can be expressed as the product of two or more integers, each of which is the sum of two squares, then r itself can also be expressed as the sum of two squares.​

Then a1 is the sum of two squares, call them a2 and b2, and a2 is the sum of two squares, call them c2 and d2. That's how a1 & a2 are related to a, b, c, and d .

Well, that's a start.

I've got to go now. I'll check back a bit later.

GOOD LUCK !

21. Jun 5, 2012

### aporter1

okay so i'm starting to prove by induction,

let a1 be related to (a2+b2) and a2 be related to (c2+d2)

so we have :

22. Jun 5, 2012

### SammyS

Staff Emeritus
Actually, let a1 = (a2+b2) and let a2 = (c2+d2)

What does the "...n(n+1)" mean?

Have you done the "base step" of n=2 ?

23. Jun 5, 2012

### aporter1

no because where do i substitute the 2 into?
i needed a n term in there to be able to put the 2 in

24. Jun 5, 2012

### SammyS

Staff Emeritus
If n=2, then $r=a_1\cdot a_2\ .$ Of course, a1 and a2 is each the sum of two squares.

What is your experience with writing proofs?

By the way: What level of mathematics is the course which this problem is from ?

25. Jun 5, 2012

### aporter1

I've taken history of math discrete math, but its been a while. Its a 400 level course, its an independent study class. I've gone to my teacher for help but I don't understand