Results 1 to 2 of 2

Math Help - Proof By Induction

  1. #1
    Newbie
    Joined
    Dec 2008
    From
    Philadelphia
    Posts
    24

    Proof By Induction

    I know induction is suppose to be easy, but this one is stumping me because it is about inequalities.

    let s_n be a positive non decreasing sequence, i.e s_n < s_n+1 for all n

    let q_n be the sequence 1/n *(s_1 + s_2 + ...+ s_n)

    prove that the sequence q_n is also non decreasing , ie q_n < q_n+1 for all n

    I was able to do the base case (obviously), and then i said assume q_n < q_n+1 for some n. and i wrote a lot of scratch but cant seem to prove q_n+1 < q_n+2 (the induction hypotheses)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2009
    Posts
    152
    Okay, this is sort of crude, but I think it works.

    q_{n+1}=\frac{1}{n+2}\left[ (n+2)q_{n+1}\right]

    =\frac{1}{n+2}[(n+1)q_{n+1} + q_{n+1}]

    =\frac{1}{n+2}[(s_1 + s_2 + \ldots + s_{n+1}) + q_{n+1}]

    \leq \frac{1}{n+2}[(s_1 + s_2 + \ldots + s_{n+1}) + s_{n+1}]

    < \frac{1}{n+2}[s_1 + s_2 + \ldots + s_{n+1} + s_{n+2}]

    =q_{n+2},

    where the fourth line follows by properties of arithmetic mean (the average of a set of values is less than or equal to the maximum of the values) (and hence q_{n+1}\leq s_{n+1}).

    EDIT: I'm not sure if this is technically an inductive proof, since it makes no use of the assumption  q_n < q_{n+1} .
    Last edited by AlephZero; July 20th 2009 at 09:55 PM. Reason: disclaimer
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum