How did you prove this without induction? The straightedge and compass question- you start a line segment of length n and you are allowed to do the following operations: 1)draw a straight line through any two points, this line can extend beyond these points 2)draw a circle with centre at any point that passes through another point Get a straightedge and compass and go to town to get an idea of what you can do. No using the measurements on the ruler. You can also find tons of info on straightedge and compass constructions in google. For 10- if you prove the r you've constructed has b>r>=0 then you're good (this follows pretty easy from what you have already). You can do this with induction on n also without relying on your earlier theorem on the existence of that integer q. It's good that you noticed this applies, but you might want to give an induction proof a shot for practice, and it's sometimes enlightening to have multiple proofs of the same things.
For number 8, it was asserted that An <= CAn-1 for all n >= 2. If you multiply all such n (that is n=2,3,4....n) together, you end up with a2a3a4.....an <= c^(n-1)a1a2a3....an-1. Dividing both sides by a2a3a4....an-1 gives An <= A1c^(n-1). Maybe this method is just induction in disguise, but it seemed like plain algebra to me.
And as for the proof of 0 <= r < b, I already assumed this was true in proving the existence of q. I merely started with r = n - qb and substituted such that 0 <= n - qb < b and worked the rest from there. Now the question is if I assumed too much to begin with, because it seems as if my argument has been turned into "IF 0 <= r < b, then q exists", but I haven't exactly "shown" that r must satisfy the inequality.
See those dots "...."? Induction took place. Of course anyone looks at what you've done and goes "well duh, of course it's true, we just multiplied a bunch of inequalities together". If you want to actually justify this process, you need to use induction as you probably haven't proven at this point that multiplying some arbitrary number of inequalities together will preserve their order (and you'd prove this by induction as well). This might seem inane and trivial, but you do need to learn how to rigorously prove the 'obvious'. Once the proofs of the 'obvious' become 'obvious' to you (i.e. you can outline the proof clearly with a couple seconds thought) then you can start getting away with not proving them in gory detail.
Oh I see where you think you are making necessary assumptions about r, the "By solving for r in the first equation and substituting in the inequality..." bit. Is this necessary to your proof? Not really. "Knowing" the answer let you come up with how to find q, but you can just start with n and b: 1)apply theorem "blah" to n/b to get q where q+1>n/b>=q. Make sure q is nonegative as required (not difficult given n>=0 and b>0) No mention of r is required to do this, we already have n and our non zero b and the old theorem. It looks a little bit mystical where it came from but that's fine. Then: 2) Define r to be r=q*b-n. We know we can do this now because we now have n, b and q. 3) prove b>r>=0. This follows easily from how q and r were chosen. 4)move on to problem 11. edit- *#$% forum parsing my inequalities annoyingly
You are already getting into college? I thought that doesn't happen until after summer vac. I think you have misread #8 though. cAn-1 is not the same as A1c^(n-1). Maybe this helps. If not I can show you how to go about it. As for #9, I wrote something which was probably wrong but the question is vague anyway. Number 11 I looked up the answer for, but it turned out to be relatively obvious. #12, I don't know but I think the inductive step for k to k + 1 must be shown for any k, not a particular k. But this seems far too simple.. The next section is relatively easy but absolute value proofs are proving mind boggling.. Don't worry about posting in here regularly though; I am two sections ahead of you right now so..
I've actually skipped ahead to see how he treats the theory of integration. It's really amazing that he manages without ever needing to mention a "limit", even though he admits that its "beyond the scope" of the book to prove the existence of general integrals in that manner. It was very good to see it addressed without relying on vague references to an infinite number of rectangles....
Here is what I did for #10. It took me a couple of hours but I think it makes sense (in fact I found out that I had put down the solution while skipipng crucial steps so I had to go back and figure it out a different way so don't mind me if it turns out to be wrong): If n = 0 then n < b because b > 0. So let q = 0 and r = 0 satisfying 0 <= r = 0 < b. Assume n = k is true for k >= 0 so that k = qb + r To prove k + 1 = qb + r for nonnegative integers q and r such that 0 <= r < b (k + 1) = qb + (r + 1) If 0 <= r + 1 < b then replace r in the original equation with the integer (r + 1) If r + 1 >= b then let q' = q + 1 > 1 and r' = (k + 1) - q'b r' = (k + 1) - q'b = (k + 1) - (q + 1) b = k + 1 - qb - b = (r + 1) - b >= 0 If r' >= b then (r + 1) - b >= b r + 1 >= 2b > 2r 1 > r This leads to contradiction since the assertion is true for n = k where r >= 0. Therefore r' < b.
I don't remember where on google I found #11 but here it is: Assume the statement is false. Then the set S of integers which are neither primes nor products of primes is not empty and by the well ordering principle, has a smallest member. Since 2 is a prime this minimum k>2. Supposek is not prime but cannot be expressed as the product of primes. k = ab, 1 < a < k and 1 < b < k. Since a and b are smaller than k however theyu must be themselves primes or products of primes. But this leads to contradiction. The uniqueness of this problem is that it cannot be solved by the usual k to k + 1 method.
shmoe how can i solve 1i on 43. |x| - |y| <= |x - y|. It probably involves proving some corollary of the triangle inequality but if not then the only way is brute forcing, which I'd rather not go through.
Alot to consider even just in this section.....as for number 12, I think the important bit is in fact that the induction was not demonstrated for arbitrary numbers, and one need only point out that the argument cannot be used to go from 1 to 2 girls. If that can't even be demonstrated, then obviously not "all" blonde haired girls in arbitrary collections have blue eyes; it doesn't work for the case of n=2.
Does this problem have anything to do with #10? For example if we needed to draw a line of length sqrt(49) with a straightedge of unit length 3, a line of length 3*2 could be drawn and then it could be asserted (but not proven?) that since the remainder (1) is less than 3 then it can also be constructed. Otherwise.. I don't know.
This kind of seems ridiculous to ask, but by what method are we supposed to "compute" the smallest integer satisfying the inequality in number 7?
#8 For 1, a(1) <= a(1) If the assertion is true for k >= 1 then a(k + 1) <= a(1)c^k To prove this: a(k) <= a(1)*c^(k-1) ca(k) <= a(1)c^k a(k+1) <= ca(k) by the property given in the problem therefore a(k+1) <= a(1)c^k
alyosha i don't think its supposed to be an analytic method. Or.. otherwise I didn't use one per se. I believe here you are required to know the binomial theorem before he presents it formally. thereofore such an integer (n1) must be >=3 since the highest power in the inequality is a 2.
Well ordering and induction are equivalent. You can rearrange this to be an induction proof. Take S(k) to be the statement "Every integer n with k>=n>1 is either prime or it can be written as a product of primes" and go from there. If Apostol doesn't cover "strong" induction you might want to look it up and prove that it's in fact equivalent to your normal form of induction (and well ordering). You can rearrange this to be the triangle inequality. Change to |x|<=|x-y|+|y| and make some substitutions. Ugg I see that I missread a little, you start with a unit length. Your straightedge has no markings. Get these tools in front of you- a straight edge, a compass and a piece of paper. Draw a line segment of some arbitrary length, not too big relative to the paper though. Declare this length to be the "unit length" and declare this line to have length 1. This is your base case as sqrt(1)=1. Can you use your tools to make a length of sqrt(2)? With this new length in hand, can you then make sqrt(3)? Now given a length of sqrt(n-1) how can you construct a length of sqrt(n)? Sometimes working through S(k-1)=>S(k) for some specific values of k (like k=2, 3, etc. however many it takes) will shed light on the general case. You should be able to make right angles with your tools. Play around with your compass and straightedge until you figure it out or get bored and look up the constructions. This isn't really vital to what you're learning in calculus, but these sorts of compass and straightedge constructions are classic problems, nice to think about, and a fairly different induction question.
