How to prove it? (apostol)

Discussion in 'Physics & Math' started by alyosha, Jun 14, 2006.

  1. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    Just a quick question shmoe. How did apostol expect us to be able to do that if he never covered strong induction in the section? it took me two days to confirm my suspicion that i had no clue how to do this problem.

    Please Register or Log in to view the hidden image!



    and im still trying to figure out for #17 how to show that if a < b then a^(1/p) < b^(1/p)
     
    Last edited: Jul 21, 2006
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    Yes, the statement you've written is true. It follows directly from the fact that the power function (.)^k is monotonically increasing for positive arguments.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    You have to prove it using the field axioms and the definition of < or >.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    For #19, I'm assuming when you tackle the n+1 case you assume the n + 1 numbers can be entirely different from the n numbers for which you assume the assertion is true. but this makes things difficult.. any help? the hint says you can assume at least a(1) > 1 and a(n+1) < 1 but as far as I can tell, a(2), a(3).. might not be the same either.
     
  8. shmoe Registred User Registered Senior Member

    Messages:
    524
    "strong induction" is essentially the same as "weak/normal induction". The nth fibonacci number is a sum of the n-1 and n-2 fib. numbers, so needing to rely on the last two rather than the last one shouldn't be too suprising.

    If b^(1/p)=< a^(1/p) then raise both sides to the power p to get b<=a, so if a < b you must have a^(1/p) < b^(1/p).

    This relies on your earlier qustion:

    Which you can prove by induction on k. Induction hyp. will give a^(k-1) < b^(k-1), multiply both sides by a to get a^k < a*b^(k-1) < b*b^(k-1) = b^k

    The n case is a statement about *any* n numbers whose product is 1. In case b) you end up with a product of n numbers, b(1)*a(2)*a(3)*...*a(n)=1, so the sum b(1)+a(2)+...+a(n)>=n, then apply the last part of the hint.
     
  9. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    I am wondering... are we only trying to get good at induction? Seems like everything is being proved by induction. Should that be the case, I would prove the "a < b => a^k < b^k" a different way than I would have done.
     
  10. alyosha Registered Senior Member

    Messages:
    121
    Alright, I'm bringing the discussion back to the binomial theorem whether you like it or not. From the induction hypothesis, its clear that multiplying both sides by (a+b) is the necessary step to n+1. Distributing the sum to both "a" and "b"
    gives you two of the original sums, one multiplied by a and the other multiplied by b. NOW, the goal appears to be showing how reasoning inductively from the other side of the equation can lead to the same conclusion. Considering the sum for n+1, and then substuting in pascals law, you end up (after distributing the sum) with two of the original n+1 sums, one involving (n,k) and the other with (n, k-1). Also, the term b^(n-k) seems necessarily changed to b^(n+1-k). ANYWAYS.


    NOW the goal seems to be to show that these two sums are equivalent to the first two from the induction hypothesis. The problem is that I seem to only be able to reason with intuitive or combinatorical ideas. Consider the sum involving (n,k) running from k=0 to k=n+1. Now, if we factor out b, the term b^(n+1-k) changes back to b^(n-k). Good. At this point, my reasoning is simply that there is one "new term" (new with respect to the induction hypothesis) involving k=n+1, which turns out to be zero (according to my graphing calculator;on paper it seems like you end up with a negative factorial that I have no idea how to interpret). So it seems that this settles it with the sum multiplied by b. Now for the sum multiplied by a.


    Consider the other sum, involving (n, k-1) running from k=0 to k=n+1.
    This has a bit more to consider. Factor out a, and the term a^k turns into a^k-1. Uh oh, seems like we are farther from our goal than when we started. In this case, the FIRST term of the sum seems to be neglectible (again a negative factorial, but this time my calculator simply says "error") So essentially we are considering k=1 through k=n+1. How are the terms behaving in light of this? a ranges from a^0 to a^n. B ranges from b^n to b^0. And, essentially, the (n,k-1) term ends up working exactly like a (n,k) term, because k ranges from 1 to n+1 rather than 0 to n. And, to wrap up, this seems like the best I can do for now to show that this sum is the same as our induction hypothesis multiplied by a. It convinces me, at least.
     
  11. alyosha Registered Senior Member

    Messages:
    121
    For proving the sum of (n,k) = 2^n where k ranges from 0 to n, using the binomial theorem, are we to just consider (2+0)^n and then the term (2^k)(0^n-k) becomes zero? It would seem like if that were the reason, (n,k) would become zero, too, and you'd have a whole sum of zeros. Obviously, though, 0^n-k =1 and is only nonzero when k=n, which brings you to the correct conclusion that 2^n is the result. However, exactly how this observation relates the expression with the binomial theorem is a little unclear to me. It would seem like this equation could be proved with the same sort of combinatorical idea I used in the proof of the binomial theorem ,WITHOUT having to actually refer back to the binomial theorem.
     
  12. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    alyosha, consider the case where a =1 and b = 1. Apply the binomial theorem.
     
  13. alyosha Registered Senior Member

    Messages:
    121
    Thanks....that makes all-too-much sense.
     
  14. shmoe Registred User Registered Senior Member

    Messages:
    524
    My kingdom for LaTeX. I'm going to try to translate what you've written using these ascii notations for sigma and the binomial ceofficients:

    sum(k=x..y,f(n))=f(x)+f(x+1)+...+f(y-1)+f(y)
    B(n,k)=n!/k!/(n-k)!


    (a+b)^n=sum(k=0..n,B(n,k)*a^k*b^(n-k))

    by the induction hypothesis. Multiply both sides by (a+b) and distribute:

    (a+b)^(n+1)=sum(k=0..n,B(n,k)*a^k*b^(n-k+1)) + sum(k=0..n,B(n,k)*a^(k+1)*b^(n-k))

    Good so far?

    Here you hit a problem. You're trying to use B(n+1,k)=B(n,k-1)+B(n,k) where it doesn't apply, this is why you ended up with 'negative factorials', something that shouldn't happen here and are undefined as far as you are concerned. Pascal's dealie is only valid if k is strictly greater than 0 and strictly less than n+1, which doesn't happen in the first and last terms of this sum (this restriction is implicit in the definitions of the binomial coefficients involved).

    Not a big problem though, remove them first:

    sum(k=0..n+1,B(n+1,k)*a^k*b^(n+1-k))
    =sum(k=1..n,B(n+1,k)*a^k*b^(n+1-k)) + B(n+1,0)*a^0*b^(n+1) + B(n+1,n+1)*a^(n+1),b^0
    =sum(k=1..n,B(n+1,k)*a^k*b^(n+1-k)) + b^(n+1) + a^(n+1)

    and now ask Pascal about the summation term to get:

    sum(k=1..n,B(n,k)*a^k*b^(n+1-k)) + sum(k=1..n,B(n,k-1)*a^k*b^(n+1-k)) + b^(n+1) + a^(n+1)

    Now you can continue as you had planned, but we'll have to stick the a^(n+1) term and the b^(n+1) term back into these sums. Which goes where? Looking at the terms of sum(k=1..n,B(n,k)*a^k*b^(n+1-k)), if we tried to stick k=0 in we'd get B(n,0)*b^(n+1)=b^(n+1). We have one of those, so


    sum(k=1..n,B(n,k)*a^k*b^(n+1-k)) + b^(n+1)
    =sum(k=0..n,B(n,k)*a^k*b^(n+1-k))

    Similarily in sum(k=1..n,B(n,k-1)*a^k*b^(n+1-k)), we can take k=n+1 and the term would be B(n,n)*a^(n+1)=a^(n+1). the net result is:

    sum(k=1..n,B(n,k)*a^k*b^(n+1-k)) + sum(k=1..n,B(n,k-1)*a^k*b^(n+1-k)) + b^(n+1) + a^(n+1)
    =sum(k=0..n,B(n,k)*a^k*b^(n+1-k)) + sum(k=1..n+1,B(n,k-1)*a^k*b^(n+1-k))

    You're now a change of indicies in the second sum away from the two sums you are after.

    Is this at all clear? I could probably convert this to a pdf or other image via latex if you like. I think your main problem was applying pascals where you couldn't.
     
  15. shmoe Registred User Registered Senior Member

    Messages:
    524
    If any of this seem like induction practice to you, then you need induction practice. It's a fundamental tool that you must have no problems with if you hope to get anywhere in maths. It's more important than your timestables, or being able to integrate by parts, or breathing really.

    Much of what's been discussed here so far have been statements about some property holding for all the naturals. These problems are interesting in their own right, irregardless of how they are proven. It's just the case that induction is quite often the most 'natural' way to go about proving a statement holds for all naturals, they are defined as an inductive set after all.
     
  16. alyosha Registered Senior Member

    Messages:
    121
    Would it be too much trouble to convert all that, shmoe? I have a feeling it will take me a while to make sense of all of that.
     
  17. alyosha Registered Senior Member

    Messages:
    121
    Ok, actually, I just read through it, and I see my mistake was applying pascal too soon.......but it still seems strange, that even though pascal may not "apply", one could still easily get the correct result by tossing out the undefined terms.
     
  18. shmoe Registred User Registered Senior Member

    Messages:
    524
    It's not too difficult to convert, but you sound like you've figured it out?

    Think about how you use Pascals to generate the next line of pascal's triangle. This is really just adding up the two terms above. The first and last terms of the row (the 1's) are special though, they are the sum of only one term above. This is essentially the same thing. The 'undefined terms' would be analagous to trying to add something from the row above that's not on the triangle.

    edit-a little more detail

    If you attempt to put in k=0 into B(n+1,k)=B(n,k-1)+B(n,k) you get:

    B(n+1,0)=B(n,-1)+B(n,0)

    The B(n,-1) is the undefined thing, toss it out and you get:

    B(n+1,0)=B(n,0)

    which is of course true, it's 1=1. Similar thing will happen if you try k=n+1.
     
  19. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    Any help on #20 of pg47? I've been workin on it for a while but it doesn't seem to follow the method of 19
     
  20. shmoe Registred User Registered Senior Member

    Messages:
    524
    #20 a) you can apply #19 to it. the product of the x_i's isn't necessarily 1, so try to adjust them until it is.
    b)prove the inequality G < M_p first, you can use part a) to do this. then apply this to the M_q < G inequality.
     
  21. alyosha Registered Senior Member

    Messages:
    121
    Schmoe, I can "see" how the indice change can be made, but must this change must be justified logically...somehow?
     
  22. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
  23. shmoe Registred User Registered Senior Member

    Messages:
    524
    You'd like something like: for a fixed integer k and sequence a(i),

    sum(i=0..n,a(i)) = sum(j=k..n+k,a(k-j)) is true for all n>=0.

    If you like you could prove this by induction on n, it should be straightforward at this point, possibly in the realm of 'obvious'.
     

Share This Page