Couple of Proofs (Regular Induction / Well Ordering)

[opt!kal]

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

Homework Statement

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

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

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?
--------------------------------

Homework Statement

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.

Homework Equations

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.

Assume that you are given a pile of n >=1 pebbles. You are to divide this
into n piles, each containing one pebble. You do this by arbitrarily splitting the pile into
two piles (not necessarily of equal size) and then successively splitting each of the resulting
piles into smaller piles until you end up with piles of size one. If at some stage you split a
pile into two piles of size r and s, then you add the product rs to a counter (which is set to
zero before this process begins). Prove, via strong induction, that no matter how you split
the piles, at the end the counter will always read n(n − 1)/2.

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!

 

[Dick]

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.

 

[exk]

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

 

[opt!kal]

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!

 

[Dick]

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?

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.

 

[opt!kal]

so i was talking to my TA again, and he basically said:

So what you want to do is draw a
really big circle, pick a point on the outside, connect your lines
which yields a 90 degree angle for you, and then *measure* off the
appropriate lengths on those bigger legs of the triangle.

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 don't know I am still unsure on that.

 

[Dick]

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.

 

[exk]

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 don't know I am still unsure on that.

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.

 

[opt!kal]

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!