Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Method of proof

  1. Jul 17, 2009 #1
    Suppose I want to show that an+1 < an one could find the derivative of the sequence and then show that it is negative for a certain domain of values for x. However is it also possible to conclusively prove that an+1 < an simply by subbing in n+1 and n and show that the inequality leads to a logical conclusion?
     
  2. jcsd
  3. Jul 17, 2009 #2
    Do you have a specific example that you are wanting help with maybe? In general, it is just like showing any other inequality. For example, let an=-n. Then since -(n+1)<-n, we know that an+1<an.
     
  4. Jul 17, 2009 #3
    Sure, how about this: Determine if an+1 is < or = to an
    [tex]a_n=\frac{n}{2^{n-1}}[/tex]

    My concern is if it is possible to assume:
    [tex] \frac{n+1}{2^n} \leq \frac{n}{2^{n-1}} [/tex], and show that it leads to the correct statement,
    [tex] \frac{1}{2} \leq \frac{n}{n+1}, \qquad n\geq 1 [/tex]?
     
  5. Jul 17, 2009 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, it is NOT possible to prove anything by assuming what you want to prove and showing that you can prove something "logical" from it. You can prove ANYTHING from a FALSE hypothesis.

    What you can do, of course, is start from the definition of your sequence and derive "an+1[/sup]< an".
     
  6. Jul 17, 2009 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    In fact, you did your proof backwards. A correct proof would be starting with

    [tex] \frac{1}{2} \leq \frac{n}{n+1}, \qquad n\geq 1 [/tex]

    which you know is correct

    and concluding


    [tex] \frac{n+1}{2^n} \leq \frac{n}{2^{n-1}} [/tex]

    Which you weren't sure (until now) whether it is correct
     
  7. Jul 17, 2009 #6
    It seems kinda like cheating because you would have to still find out that [tex] \frac{1}{2} \leq \frac{n}{n+1}, \qquad n\geq 1 [/tex] by first guessing and playing around?

    I mean why do you have to start off backwards it seems like in almost all cases where i have used this method (of guessing the inequality and then fixing it to yield a correct statement) all the time the steps are reversible and lead to correct conclusion both ways, i cannot see a time where this would not be correct. (maybe by some division by zero, but i have not encountered such a case)
     
  8. Jul 17, 2009 #7

    You wouldn't guess and play around to derive the inequality [tex] \frac{1}{2} \le \frac{n}{n+1} [/tex] for n >= 1.

    If n >= 1,then 1/n <= 1. Add 1 to both sides then multiply both sides by n, which gives n + 1 <= 2n, implying that 1/2 <= n/(n+1).

    As for your other question, consider this example. 1 < 2. Multiplying by 0 gives 0 < 0, which is obviously not true. If you are going to assume the premise, then reverse your steps to arrive at a valid proof, you have to be VERY careful about what you do. In fact once you finish reversing the steps and writing down your proof, you should look over the proof to make sure you haven`t done anything silly, like what I did in my counter-example.
     
  9. Jul 17, 2009 #8
    You have to be careful. I've once made the error myself.
    Suppose you have to prove some statement S. Then it is not a valid proof to:
    (1) start with S
    (2) do some manipulations
    (3) and arrive at a true statement.

    For example:
    (1) Statement S: 5 = 4
    (2) Manipulations: 0*5 = 4*0
    => 0 = 0
    (3) Since we arrived at a true statement (0 = 0 is true), the statement S is correct.

    But the above is of course wrong! This is what HallsOfIvy mentioned.

    ---

    The way you start proofs is to write down FIRST what you already know is true, e.g.
    we first write down n>=1 (as JG89 mentioned).

    It seems a little "magic" and you could ask why I should start with n>=1. Of course, you figured this out by "working backwards" from 1/2 <= n/(n+1). But still, you write down a true statement first and derive something from it.

    In mathematics you will often see proofs where they start with some "magical" assumption. For example in delta-epsilon proofs they just start with some delta and you ask yourself how they thought of that delta. Of course, they worked backwards, but you don't include this "working backwards" in your proof.
     
    Last edited: Jul 17, 2009
  10. Jul 17, 2009 #9
    First try to find the sign of [itex]a_n-a_{n+1}[/itex] i.e positive or negative.

    [tex]a_n=\frac{n}{2^{n-1}}[/tex]

    [tex]a_n-a_{n+1}=\frac{n}{2^{n-1}}-\frac{n+1}{2^{n}}=\frac{2n}{2^n}-\frac{n}{2^n}-\frac{1}{2^n}=\frac{n-1}{2^n}[/tex]

    [tex]\frac{1}{2^n} \geq 0[/tex]

    and

    since [itex]n\geq 1 [/itex], also [itex]n-1 \geq 0 [/itex]

    so both are positive, and [itex]+/+=+[/itex]

    and [itex]a_n-a_{n+1} > 0 [/itex] so [itex]a_n>a_{n+1}[/itex]

    Regards.
     
    Last edited: Jul 17, 2009
  11. Jul 17, 2009 #10
    It now makes more sense to me, at the start I thought it is useless beacuse of course you would have had to reach the conclusion [tex] \frac{1}{2} \leq \frac{n}{n+1}, \qquad n\geq 1 [/tex] by working forwards (most likely, at least this way is the simplest), and then again work backwards to actually prove it true. I guess this is what first confused me beacuse it seemed almost conclusive that every step is reversible, and therefore I saw starting from the back then working a waste of time, but now i know you cannot take this assumption for granted as Edgardo points out in his example.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Method of proof
  1. Proof of Phasor Method (Replies: 8)

Loading...