1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Proof by induction

  1. Oct 15, 2007 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    http://img87.imageshack.us/img87/469/17317851uu7.jpg [Broken]

    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.
    Last edited by a moderator: May 3, 2017
  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
    Last edited by a moderator: May 3, 2017
  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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook