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