1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by induction of the sum of 2 squares

  1. Jun 2, 2012 #1
    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. jcsd
  3. Jun 3, 2012 #2
    the r=a1,a2,a3..an is confusing. can you clarify?
     
  4. Jun 3, 2012 #3
    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
     
  5. Jun 3, 2012 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Hello aporter1. Welcome to PF !

    So, does a1,a2,a3...an refer to a string of integers?
     
  6. Jun 3, 2012 #5
    yes i believe so
     
  7. Jun 3, 2012 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Then what does "any integer r= a1,a2,a3...an" mean? A string of integers is not equal to an integer.
     
  8. Jun 3, 2012 #7
    i attached the problem. Its a Jpeg file and it's questionn number 8. Maybe that will help everyone out.
     

    Attached Files:

  9. Jun 3, 2012 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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 [itex](a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\,,[/itex] prove by induction that any integer [itex]r=a_1a_2\dots a_n\,,[/itex] 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 .
     
  10. Jun 4, 2012 #9
    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.
     
  11. Jun 4, 2012 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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 [itex]a_1,a_2,\dots a_{k+1}[/itex] appropriately. So you assume that the product [itex]a_1a_2\dots a_k[/itex] is also the sum of two squares.

    What does that tell you about [itex]\left(a_1a_2\dots a_k\right)a_{k+1}\ ?[/itex]
     
  12. Jun 4, 2012 #11
    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.
     
  13. Jun 4, 2012 #12

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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 ?
     
  14. Jun 4, 2012 #13
    so i start with

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

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

    Then I show true for n=k
     
  15. Jun 5, 2012 #14
    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.
     
  16. Jun 5, 2012 #15

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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 [itex](a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\ .[/itex]
     
  17. Jun 5, 2012 #16
    Oh..
     
  18. Jun 5, 2012 #17
    so am i on the right track?

    r=a1a2...an= (ac−bd)2+(ad+bc)2
     
  19. Jun 5, 2012 #18

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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?​
     
  20. Jun 5, 2012 #19
    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.
     
  21. Jun 5, 2012 #20

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
    [itex](a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2\,.[/itex]​
    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, [itex]r=a_1a_2\dots a_n\,,[/itex] 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 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 !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction of the sum of 2 squares
Loading...