Results 1 to 2 of 2

Math Help - proving (by induction)

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    23

    proving (by induction)

    Suppose the numbers a0,a1,a2,....,an satisfy the following conditions:

    a0= 1/2, ak+1 =ak + (1/n) ((ak)^2) for k=0,1,2,...,n-1.

    Prove that (n+1)/(
    2n-k+2) <ak < (n)/(2n-k )


    for k=1,2,3,....,n



    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    The statement doesn't make sense for n=0 !

    We'll prove it for every natural number n>0 by induction on k.

    Base case: k=1.

    a_1 = \frac{1}{2}+\frac{1}{4n} = \frac{2n+1}{4n}

    \frac{n+1}{2n-1+2} < \frac{2n+1}{4n} iff 4n(n+1) < (2n+1)(2n+1) iff 4n^2+4n < 4n^2+4n+1 and this is true for every n>0.

    \frac{2n+1}{4n} < \frac{n}{2n-1} iff 4n^2-1 < 4n^2 and this is true for every n>0.

    Base case verified.


    Let for arbitrary n>0

    \frac{n+1}{2n-k+2}<a_k<\frac{n}{2n-k} \; \; \; \; \; (1)

    hold for some 0<k<n . We want to show that (1) also holds for k+1, i.e. we want

    \frac{n+1}{2n-k+1} < a_k+\frac{1}{n}a_k^2 < \frac{n}{2n-k-1} \; \; \; \; \; (2)

    to hold.
    From the second inequality in (1) we have a_k+\frac{1}{n}a_k^2 < \frac{n}{2n-k} + \frac{1}{n} \left(\frac{n}{2n-k}\right)^2 = \frac{n(2n-k+1)}{(2n-k)^2} and this is strictly less than  \frac{n}{2n-k-1} iff 4n^3-4kn^2+k^2n-n < 4n^3-4kn^2+k^2n which is equivalent to -n<0 which is true because n>0.

    So the second inequality in (2) is verified.

    From the first inequality in (1) we have a_k+\frac{1}{n}a_k^2  > \frac{n+1}{2n-k+2}+\frac{1}{n}\left(\frac{n+1}{2n-k+2}\right)^2 = \frac{(n+1)(2n^2-kn+3n+1)}{n(2n-k+2)^2} and this is strictly greater than \frac{n+1}{2n-k+1} iff 4n^4-4n^3k+12n^3+k^2n^2-8kn^2+13n^2+k^2n-5kn+6n-k+1>

    > 4n^4-4n^3k+12n^3+k^2n^2-8kn^2+12n^2+k^2n-4kn+4n which is equivalent to n^2-kn+2n-k+1>0.

    Now because k<n we have n^2-kn+2n-k+1> n^2-n^2+2n-n+1 = n+1 > 0, no doubt.

    So the first inequality in (2) is also verified and thus the induction step is completed and the proof is finished.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving an inequation with induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 9th 2011, 12:17 PM
  2. Using my assumption when proving by induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 28th 2010, 04:05 AM
  3. Need help proving mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 29th 2009, 09:16 AM
  4. few problems on proving using induction
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: March 22nd 2009, 03:00 PM
  5. Need help proving!! Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 07:38 PM

Search Tags


/mathhelpforum @mathhelpforum