Proof by induction of the sum of 2 squares

[aporter1]

Homework Statement

(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

Homework Equations

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

 

[ArcanaNoir]

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

 

[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

 

[SammyS]

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

Hello aporter1. Welcome to PF !

So, does a₁,a₂,a₃...a_n refer to a string of integers?

 

[aporter1]

yes i believe so

 

[HallsofIvy]

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

 

[aporter1]

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

 

[SammyS]

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=1²+1², 5=1²+2², 8=2²+2², 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 .

 

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

 

[SammyS]

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.

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}\ ?$
​

 

[aporter1]

so i start by setting up the problem as:
r=a1a2...an+a(n+1)=(ac-bd)^2+(ad+bc)^2
now,
what? I'm stuck.

 

[SammyS]

so i start by setting up the problem as:
r=a1a2...an+a(n+1)=(ac-bd)^2+(ad+bc)^2
now,
what? I'm stuck.

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

For exponents, use the X² icon.

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

There should be no addition sign in a₁a₂...a_n+a_n+1. It should be a₁a₂...a_na_n+1, where all the a_k's are multiplied together.

If you assume your conjecture holds for n, what can you say about the number a₁a₂...a_n ?

 

[aporter1]

so i start with

r=a₁a₂...a_n= (ac−bd)²+(ad+bc)²

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

Then I show true for n=k

 

[dimension10]

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

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.

 

[SammyS]

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.

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

 

[dimension10]

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

Oh..

 

[aporter1]

so am i on the right track?

r=a1a2...an= (ac−bd)²+(ad+bc)²

 

[SammyS]

so i start with

r=a₁a₂...a_n= (ac−bd)²+(ad+bc)²

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

Then I show true for n=k

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 a₁ and a₂ ?

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=1²+1², 5=1²+2², 8=2²+2², for r=160 .

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

 

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

 

[SammyS]

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.

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.

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=1²+1², 5=1²+2², 8=2²+2², 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 .

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. (a²+b²), which is the sum of two squares, a² and b²; times (c²+d²), which is the sum of two other squares, c² and d². The identity says that the resulting product is equal to (ac-bd)²+(ad+bc)², which is the sum of two squares, (ac-bd)² and (ad+bc)².

(I really wish they hadn't used the variable name, a, in two different ways; here as a, later as a_i 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.​

To do this by induction, start with n = 2.

Then a₁ is the sum of two squares, call them a² and b², and a₂ is the sum of two squares, call them c² and d². That's how a₁ & a₂ 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 !

 

[aporter1]

okay so I'm starting to prove by induction,

let a₁ be related to (a²+b²) and a₂ be related to (c²+d²)

so we have :

r=(a²+b²)(c²+d²)...n(n+1)= (ac-bd)²+(ad+bc)²

 

[SammyS]

okay so I'm starting to prove by induction,

let a₁ be related to (a²+b²) and a₂ be related to (c²+d²)

so we have :

r=(a²+b²)(c²+d²)...n(n+1)= (ac-bd)²+(ad+bc)²

Actually, let a₁ = (a²+b²) and let a₂ = (c²+d²)

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

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

 

[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

 

[SammyS]

If n=2, then $r=a_1\cdot a_2\ .$ Of course, a₁ and a₂ 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 ?

 

[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

 

[Curious3141]

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

Start by defining a set S of all integers that can be expressed (not necessarily uniquely) as the sum of the squares of two integers.

Small letter "a"s refer to some elements of S, while big letter "A"s refer to the product of those elements.

The inductive hypothesis (the part you assume as true to start your proof) is that for some k, the product A_k = a₁a₂...a_k $\in$ S

which means that A_k can be written as (m² + n²), for some integers m and n.

You now have to prove, using that assumption and with the help of the identity given, that the product of A_k with another integer (call it a_k+1) that's the sum of two squares (call that (p² + q²), for some integers p and q), will again be expressible as a sum of two squares.

Formally, you need to establish that A_k+1 = A_k.a_k+1 $\in$ S, where a_k+1 $\in$ S.

This part is just simple algebra. Can you manage it?

The last step (or first step, if you prefer) of proving that A₁ $\in$ S is trivial since A₁ is simply equal to a₁, where the latter is already defined as the sum of two squares.

 

[aporter1]

okay but what I'm confused with is how do I end up substituting n in?

 

[aporter1]

so I'm thinking this is how i start,

r= (a²+b²)(c²+d²)...n=(ac-bd)²+(ad+bc)²

am i on the right track?

 

[SammyS]

so I'm thinking this is how i start,

r= (a²+b²)(c²+d²)...n=(ac-bd)²+(ad+bc)²

am i on the right track?

No. It appears that you don't fully understand the notation here.

If n=2,

then r = a₁∙a₂​

If n=3,

then r = a₁∙a₂∙a₃​

If n=4,

then r = a₁∙a₂∙a₃∙a₄​

If n=5,

then r = a₁∙a₂∙a₃∙a₄∙a₅​

If n=6,

then r = a₁∙a₂∙a₃∙a₄∙a₅∙a₆​

Get the picture?

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

Now for a concrete example. I suggested that you do the ones in the text, a few posts ago.

Suppose n=3 and

a₁=25

a₂=5

a₃=61​

Then r = 25∙5∙61 = 7625 .

How can we write 7625 as the sum of two squares?

One way:

Look at 25∙5 as 125 , so r = 125∙61 .

125 = 10² + 5²

61 = 5² + 6²

The algebraic identity says (10² + 5²)(5² + 6²) = (10∙5 - 5∙6)² + (10∙6 + 5∙5)² = 20² + 85² = 400 + 7225 = 7625​

Another way:

Look at 5∙61 as 305 , so r = 25∙305 .

25 = 3² + 4²
 
305² = 17² + 4²   (If we needed to, we could use the algebraic identity figure this out. Actually, that's how I did it!)

The algebraic identity says that (3² + 4²)(17² + 4²) = (3∙17 - 4∙4)² + (3∙4 + 4∙17)² = 35² + 80² = 1225 +6400 = 7625 . ​

 

[Curious3141]

so I'm thinking this is how i start,

r= (a²+b²)(c²+d²)...n=(ac-bd)²+(ad+bc)²

am i on the right track?

No. "n" in the way you used it *usually* refers to the n-th positive integer (i.e, the number "n" when you're counting 1,2,3,4,...n).

In a mathematical induction proof, the inductive step always involves this "IF it's (assumed) true for some n, THEN it can be proven true for (n+1)" step. You might be confused into thinking this means you're proving a property for some integer (n+1) - but this is not so. "n" is just an index of a general term $a_n$, and the exact meaning of the terms can vary depending on the problem. So if you're proving something about all positive integers, then $a_n = n$. If you're proving something about positive even integers, then $a_n = 2n$. And if you're proving something about prime numbers, then $a_n$ is the nth prime number. And so forth.

In this problem, you're proving something about numbers that are sums of squares, so $a_n$ simply refers to the n-th number on a list that's made up of numbers that are all sums of squares. The slightly confusing thing about this problem is that it may not be possible to order $a_1, a_2, a_3,...,a_n$ consecutively, but it really doesn't matter. The subscripts are only used to distinguish the terms in the sequence.

[So here, n is being used in the context of a subscript (like a counting index) in the product of numbers, each of which is called "a" (just like SammyS used it). In my post, I used "k" as the subscript (and "n" to mean something else entirely), but here, I'll stick to SammyS's meaning of "n".]

What you want to write down is a product of certain numbers (called "a" with various subscripts) that are all individually sums of squares. Note that $a_1, a_2, a_3,...,a_n$ are not necessarily consecutive integers, and they may not even be increasing in one direction. It doesn't matter. But the way you express that product (I'm calling the product big "A") is:

$$A_n = a_1a_2a_3...a_n$$.

In mathematical induction, you start with an assumption. Here the assumption is that $A_n$ can be written as the sum of two squares. Let's call those squares $p^2$ and $q^2$, where p and q are integers. So you assume this to be true:

$$A_n = p^2 + q^2$$

What you now *need to prove* is that if you take any other integer (call it $a_{n+1}$) that's *also* the sum of two squares and multiply it by $A_n$, you can express that product as the sum of two squares also.

Because $a_{n+1}$ can be written as $s^2 + t^2$, where s and t are integers, the product:

$$A_na_{n+1} = (p^2 + q^2)(s^2 + t^2)$$

Can you now use the identity given to express the RHS (right hand side) of that equation as the sum of two squares? Remember that "a" in the identity refers to something else - just another variable (it's unfortunate that they used the same symbol, but what can you do?).

Once you've done this, you've proved that assuming $A_n$ can be written as the sum of two squares, the product $A_{n+1}$ which is $A_na_{n+1}$, is also so expressible. That completes the inductive step.

The base step just involves a verification that the proposition (what you're trying to prove) holds for n = 1. And as I mentioned, this part is trivial, because the product here is just $a_1$, which is already defined to be the sum of two squares.

SammyS suggested a base step of n = 2, which involves a little algebra to prove that $a_1a_2$ is expressible as the sum of two squares. Frankly, I think this is unnecessary, but you can do it this way if you wish.

 

[aporter1]

so I've gone along with

assume: r_k=(a²+b²)
if, r_k+1=(a²+b²)(c²+d²)=(ac-bd)²)+(ad+bc)²

 

[SammyS]

so I've gone along with

assume: r_k=(a²+b²)
if, r_k+1=(a²+b²)(c²+d²)

Then r_k+1=(ac-bd)²)+(ad+bc)²

Is more like it.

 

[aporter1]

so I'm on the right track for the right side then?

 

[SammyS]

so I'm on the right track for the right side then?

What do you mean by "the right side" ?

 

[aporter1]

(ac−bd)2+(ad+bc)2