Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Proof By Induction

  1. #1
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1

    Proof By Induction

    Can somone show me how to lay out an answer for this question:


    The sequence of real numbers u_1, u_2, u_3, ... is such that u_1 = 5.2 and u_{n+1} = \frac{6u_n +10}{u_n +3}. Prove by induction that u_n>5, for ne+.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello

    Quote Originally Posted by Air View Post
    Can somone show me how to lay out an answer for this question:


    The sequence of real numbers u_1, u_2, u_3, ... is such that u_1 = 5.2 and u_{n+1} = \frac{6u_n +10}{u_n +3}. Prove by induction that u_n>5, for ne+.
    Hmm what do you think of that :

    u_{n+1}=\frac{6u_n+10}{u_n+3}=6-\frac{8}{u_n+3}



    (you can do the basis and set up the induction hypothesis, right ? if not, just ask)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post
    Hello



    Hmm what do you think of that :

    u_{n+1}=\frac{6u_n+10}{u_n+3}=6-\frac{8}{u_n+3}



    (you can do the basis and set up the induction hypothesis, right ? if not, just ask)
    Induction hypothesis?

    My teacher said for these question the layout is important to get someone to understand the proof so can you also show how you would lay out an answer for this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    u_1=5.2>5, so the inequality stands for n=1.
    Now, suppose u_n>5 and we have to prove that u_{n+1}>5
    u_{n+1}-5=\frac{6u_n+10}{u_n+3}-5=\frac{u_n-5}{u_n+3}>0
    Then u_{n+1}>5.
    Thus u_n>5, \ \forall n\geq 1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Air View Post
    Induction hypothesis?

    My teacher said for these question the layout is important to get someone to understand the proof so can you also show how you would lay out an answer for this?
    Ok, there are three main steps in an induction proof

    Preliminary : state the induction property.

    u_n>5 \quad \forall n \in \mathbb{Z}^+
    This is mostly for yourself, to clear out the view.

    1st step : the basis.
    You have to check that this is true for the very first term. Here, because we are working on \mathbb{Z}^+, it will be u_1.
    Is u_1>5 ? Yes. So the basis is verified.

    2nd step : the inductive step.
    Induction hypothesis : assume that the property is true for a rank n.
    --> u_n>5

    Then, prove that if this is verified for a rank n, it will be for the following rank, n+1.


    --> Using the hypothesis that u_n>5, prove that a_{n+1}>5

    In most of the induction exercises, this proof will require you to go back to the recursive definition of u_n


    ------------
    Is it clear ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post
    Is it clear ?
    Yes!

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Basis :
    u_1=5.2 > 5
    Hence the basis is verified

    Inductive step :
    Let's assume that u_n>5. And let's prove that u_{n+1}>5.

    \begin{aligned} u_{n+1} &=\frac{6u_n+10}{u_n+3} \\<br />
&=\frac{6u_n+18-8}{u_n+3} \\<br />
&=6-\frac{8}{u_n+3} \end{aligned}

    u_n>5 \implies u_n+3 >8 \implies \frac{1}{u_n+3}<\frac 18 \implies \frac{-8}{u_n+3}>-1

    \implies u_{n+1}=6-\frac{8}{u_n+3}>6-1 \implies u_{n+1}>5 \ \square


    So the inductive hypothesis is verified, hence the property is true for all n \in \mathbb{Z}^+

    -----------------

    This is how I was taught to write in a test
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post

    u_n>5 \implies u_n+3 >8 \implies \frac{1}{u_n+3}<\frac 18 \implies \frac{-8}{u_n+3}>-1
    u_n>5 \implies u_n+3 >8

    How did get get that? ^
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Air View Post
    u_n>5 \implies u_n+3 >8

    How did get get that? ^
    Adding both sides by 3 o.O
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Another question (Prove by induction):

    \sum^n_{r=1} r2^r = 2[1+(n-1)2^n]

    I did (but ended up at a dead end):

    Quote Originally Posted by Myself
    Let n=1

     \therefore \sum^1_{r=1} (1)2^{(1)} = 2[1+((1)-1)2^{(1)}]

     LHS=2; RHS=2 \therefore true for n=1

    Assume true for n=k

     \therefore \sum^k_{r=1} r2^r = 2[1+(k-1)2^k]

    Consider n=k+1

     \therefore \sum^{k+1}_{r=1} r2^r = 2[1+(k)2^{k+1}]

     \equiv \sum^k_{r=1} r2^r + (k+1)

    \therefore  = 2[1+(k-1)^{2k}] + k+1

     \therefore = 2+2(k-1)^{2k} + (k+1)

     \therefore = 2+2[(k-1)^k]^2 + (k+1)
    Can I have help on how to alter it to correct proof? ^
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Unfortunately, I can't quote what you have quoted yourself

    It's not really correct to write this :

    \sum^1_{r=1} (1)2^{(1)}

    Write \sum_{r=1}^1 r2^r=(1)2^1=2

    And then your working
    ------------------------
    For this line :
    <br />
\therefore \sum^{k+1}_{r=1} r2^r = 2[1+(k)2^{k+1}]<br />
    say that this is what you want to prove. The therefore sign shouldn't be here, because you haven't proved it yet.
    This should be in your draft paper, for that you can see what you have in mind, what result you should find.

    ------------------------
    \sum^{k+1}_{r=1} r2^r=\left(\sum^{k}_{r=1} r2^r \right)+(k+1){\color{red}2^{k+1}}

    But you had the good idea =)

    =2[1+(k-1)2^k]+(k+1)2^{k+1}

    =\textbf{2}[1+(k-1)2^k]+(k+1) \cdot \textbf{2} \cdot 2^k

    Factoring it :

    =2 \left(1+(k-1)2^k+(k+1)2^k\right)

    Can you continue ?




    Edit : another mistake, for this line

    \therefore = 2[1+(k-1)^{2k}] + k+1
    why did you put to the power 2k ? it was a multiplication by 2^k, which is not the same ^^
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post


    =\textbf{2}[1+(k-1)2^k]+(k+1) \cdot \textbf{2} \cdot 2^k
    Why did you multiply by 2?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Air View Post
    Why did you multiply by 2?
    I didn't

    I had 2^{k+1}, so I made appear 2, in order to have a common factor with \textbf{2}[1+(k-1)2^k].

    2^{k+1}=2^k \cdot 2^1=2 \cdot 2^k

    Is it clear for the other points ? ^^
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post
    I didn't

    I had 2^{k+1}, so I made appear 2, in order to have a common factor.

    2^{k+1}=2^k \cdot 2^1=2 \cdot 2^k

    Is it clear for the other points ? ^^
    Yes, its clear. The other 2 is just from the original series.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Sep 2007
    Posts
    528
    Awards
    1
    Quote Originally Posted by Moo View Post
    Factoring it :

    =2 \left(1+(k-1)2^k+(k+1)2^k\right)

    Can you continue ?

    I opened up the bracket :

    2(1+k2^k - 2^k +k2^k + 2^k)

    2(1+2k2^k)

    ?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum