1. Not finding help here? Sign up for a free 30min 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!

Couple of Proofs (Regular Induction / Well Ordering)

  1. Apr 30, 2008 #1
    [SOLVED] Couple of Proofs (Regular Induction / Well Ordering)

    Hi there everyone, I've been having a bit of trouble of solving these questions, so any help would be greatly appreciated:

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

    1: Prove, via regular induction, that it is possible to draw a line-segment of length exactly sqrt(n) using just a ruler and a compass for all integers n >= 1.
    (Note that certain numbers like sqrt(2) and sqrt(3), etc. have infinitely long decimal representations, so they cannot be simply be measured off on a ruler.)

    2. Relevant equations

    HINT: You may find the following geometric fact useful: If C is any circle and t = abc is any triangle inscribed in C such that ac is a diameter and b is on the circumference, thn <abc = 90 degrees.

    3. The attempt at a solution

    So I know that through regular induction that the basis step should be n = 1; so the sqrt(1) is simply 1, which can be measured on a ruler. So for the Inductive step we assume that P(k) is true, and we need to show that P(k+1) is true, i.e, sqrt(k+1) can be measured drawn with a ruler and compass.
    To tell you the truth, I really have no idea on how to tackle this problem. The only thing that I know is that if we do inscribe a triangle within a circle, then the only thing that I can feel certain about stating is that the diameter must be k, and I'm guessing that through the Pythagorean theorem, I have to show that the hypotenuse must be sqrt(k+1). But does that show that it can be drawn? And how would I go about showing that?
    --------------------------------

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

    2: Prove the following directly using the well-ordering principle ( do not use induction): Every integer n >= 1 can be written as the sum of distinct powers of 2. Be sure to state clear how you use well-ordering in your proof.
    2. Relevant equations
    3. The attempt at a solution
    To be honest, I don't even know how to start this problem. I met with my T.A and I know that I have to prove this by a contradiction using well ordering, and that I can rewrite k and k - 1 +1, but that's it really. Any help is appreciated.

    ------------------

    I have one more question, it's just making sure that my cases are correct.

    Just to make sure, when proving the P(k+1) case, I can split up the k + 1 pile as r and (k+1)-r right? so the product of those two is kr + r - r^2. and then when I split up those two piles, I know that each of those piles are less than k, and due to the Inductive Hypothesis (which I left out here) I can write each of those splits as r(r-1)/2 and [(k+1)-r][([k+1]-r)+1]/2 and then I simply add these products together to get my k+1 counter result right (which should be (n+1)n/2 I think)?

    Anyways, thanks in advance!
     
  2. jcsd
  3. Apr 30, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, so you can draw a segment of length sqrt(n), right? From the inductive hypothesis. Do so. From there you can certainly construct a perpendicular segment of length 1, yes? What's the length of the hypotenuse? I think this is what the hint is pointing towards, in a maybe somewhat cryptic manner.
     
  4. Apr 30, 2008 #3

    exk

    User Avatar

    as Dick said use the fact that the sqrt(diameter)^2=x^2+y^2 and go from there.

    for your second question. The well ordering principle guarantees a least element in an ordered integral domain. Suppose a set S of things that can't be described as a sum and then let s be the least element. What can you say about s-1 and (s-1)+1

    for the third question I think your approach is correct, but there is some confusion as to what you have to prove. You need to show that the sum of all products of the form r*s will eventually be n(n-1)/2 and furthermore you need Strong Induction, which will likely make the proof easier.
    See this for some info on proof by strong induction: http://www.cc.gatech.edu/home/idris/AlgorithmsProject/ProofMethods/Induction/StrongInduction.html
     
  5. Apr 30, 2008 #4
    Ahh I see what you're saying, because we proved P(1) in the basis, and for the P(K+1) case we can draw a diameter of k within the circle, we simply let the P(1) intersect P(k) since we assume we can draw these, and they form a 90 degree angle, and basically apply Pythagorean theorem to get the hypotenuse right? but doesn't that just end up as k+1 and not the sqrt(k+1) that we are trying to end up with?


    EDIT:
    Oops, I just realized that I made a mistake on the answer I was trying to check the product [(k+1)-r][([k+1]-r)+1]/2 should actually be [(k+1)-r][([k+1]-r)-1]/2. Sorry about that. exk I apologize I should have mentioned that we are supposed to solve by strong induction. So basically the INductive Hypotheis is going to state that P(j) is true for all positive integers j<=k right? So P(1), P(2), P(3),....P(k) are assumed to be true correct? so for solving P(k+1), I'm supposed to replace the n's in n(n-1)/2 with (k+1) right? Or is that an illegal move when doing strong induction. Thanks!
     
    Last edited: Apr 30, 2008
  6. May 1, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Not unless you are using a different Pythagorean theorem than I am. I wouldn't think of think of the circle first. Draw a segment of length 2*sqrt(n) and construct the perpendicular bisector. Now mark off a segment of length 1 along the bisector.
     
    Last edited: May 1, 2008
  7. May 1, 2008 #6
    so i was talking to my TA again, and he basically said:
    Which is basically dick has said, but my only question is does anyone think they know what he means by pick a point on the outside?

    Also, exk, for number two, Since k would be the least element that could not be written as distinct powers of two, then k-1 should be right? so then we (k-1) +1 would be something that can be written as a sum of distinct powers of two, and 1 which we proved in the basis right? But can we simply say adding them together will result in k, which means out assumption that there exists a least element within the set is false? I dunno im still unsure on that.
     
  8. May 1, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The only function of the big circle is to construct a pair of segments intersecting at a 90 degree angle. There are certainly other ways to do that. The geometry theorem he's referring to says that if an angle has it's vertex on a circle and the endpoints of a diameter of the circle are on the sides, then it's a right angle.
     
  9. May 1, 2008 #8

    exk

    User Avatar

    Exactly. Note: since k-1 can be written as a sum of powers of 2 and 1=2^0 then k can be written as sum of powers of 2. Since the k is part of the set that was assumed to contain all numbers that can't be written as sum of powers of 2 you get a contradiction; thus you show that the set S is empty and therefore all integers can be written as a sum of powers of 2.
     
  10. May 1, 2008 #9
    Okay so for the square root problem, my inductive step is basically that I can use the compass to create a circle, and since we assumed that we could draw sqrt(k) we can simply make two perpendicular lines that intersect at a 90 degree angle, and from the basis we can just mark off one from that, and do pythagorean theorem, and we end up with the hypotenuse. Awesome thank you guys!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?