1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by induction

  1. Oct 15, 2007 #1

    ar6

    User Avatar

    1. The problem statement, all variables and given/known data
    [​IMG]


    2. Relevant equations



    3. The attempt at a solution

    First I have to show that P(1) is true
    |a1| ≤ |a1| This is true

    Assume above is true for all n.

    Show that

    |∑i=1n+1 ai| ≤ n+1∑i=1 |ai|


    |a1 + a2 + a3…+ an + an+1| ≤ |a1| + |a2| + |a3| +…+ |an| + |an+1|

    |∑i=1n ai + an+1| ≤ n+1∑i=1 |ai| + |an+1|

    assuming I'm on the right track. How can i proceed. This problem is so abstract its driving me crazy. Sorry for formatting.
     
  2. jcsd
  3. Oct 16, 2007 #2
    you have to arrive at the last equation using the preceding equation.
    Lets start with the left hand side of last equation.
    |a1 + a2 + a3…+ an + an+1|≤|a1 + a2 + a3…+ an |+ |an+1|
    ....................................{ since it is valid for n=2}
    |a1 + a2 + a3…+ an + an+1|≤|a1| + |a2 |+ |a3|+…+ |an |+ |an+1|
    .....................................{since valid for n=n(seond last equation i your post)}

    Keep Smiling
    Malay
     
  4. Oct 16, 2007 #3
    You use a strong induction. Assume true for all k<n. Then

    [tex]\left|\sum_i a_i\right|=\left|\sum_{i=1}^{n-1}a_i +a_n\right|[/tex]

    You should see where to go from here.


    Problems like these are often trivial inductions. Like, for example, showing that taking the intersection of two open sets is open immediately implies that the finite intersection of open sets is always open. Why? Well, for n=3 we have (A n B)nC but we showed AnB is open! So we just repeatedly use this fact.

    It's the same thing here, really.

    Edit: If you know nothing about open sets, completely disregard.
     
    Last edited: Oct 16, 2007
  5. Oct 16, 2007 #4

    learningphysics

    User Avatar
    Homework Helper

    You should demonstrate that it is true for n = 2...

    MalayInd showed the main inductive step which is valid for n+1>2 but not for n+1 = 2.
     
  6. Oct 16, 2007 #5
    for n+1=2, it reduces to triangle inequality.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...