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

Tags:
  1. Apr 7, 2017 #1
    1. The problem statement, all variables and given/known data
    The sequence of positive numbers ##u_1,u_2,u_3...## is such that ##u_1<4## and ##u_{n+1}= \frac{5u_n+4}{u_n+2} ##
    i. By considering ##4-u_{n+1} ##, prove by induction that ##u_1<4## for ##n\geq 1##
    Mod note: The above is incorrect. In a later post the OP revised this to
    3. The attempt at a solution
    I have never been introduced to these types of backward induction so I am not aware of the statements I have to make and prove. I do get the general idea that it's like finding the limit of ##4-u_{n+1} ## as ##u_n \rightarrow 4## and then say that since as the upper limit of the function is 0, then it must be smaller than 0. So it would be very helpful if I am given an outline on how to solve this.
     
    Last edited by a moderator: Apr 8, 2017
  2. jcsd
  3. Apr 7, 2017 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    How is this "backward induction"?


    It's induction, so first do the base case.

    Use the suggestion: Consider ##4-u_{2} ## .
     
  4. Apr 8, 2017 #3
    I used the phrase "backward induction" in the sense that for a general induction problem we try to show that if a statement ##P(n)## can be converted into a ##P(n+1)## statement using allowed operations then the statement is true. Here we are supposed to use the concept in a reverse.

    Now to your suggestion,
    $$\ 4-u_{2}=4-u_{2} $$
    $$\ 4-u_{2}=4- \frac{5u_1+4}{u_1+2} $$
    $$\ 4-u_{2}=4-\frac{5+\frac{4}{u_1}}{1+\frac{2}{u_1}} $$
    $$\ 4-u_{2}>4-\frac{5+1}{1+1/2} $$
    $$\ 4-u_{2}>4-\frac{6}{3/2} $$
    $$\ 4-u_{2}>0 $$
    $$\ 4>u_{2} $$
    Is this correct? If yes what I have to do next?
    And one more thing, Can I just use the given statement ##u_1<4## as my base case?
     
  5. Apr 8, 2017 #4
    How do you "use the concept in reverse"? The description you gave, ##P(n)\Longrightarrow P(n+1)## is The principle of induction (in ##\mathbb N## at least).
     
  6. Apr 8, 2017 #5
    Well in most questions we try to convert the statement ##P(n) ## into ##P(n+1)## but here aren't we trying to convert ##P(n+1)## into ##P(n)##? If no, then probably my analogy is incorrect. Please guide me how to solve the remaining part.
     
    Last edited: Apr 8, 2017
  7. Apr 8, 2017 #6
    Edit: nvm
    You are used to induction working in the normal way, if it holds for ##n##, then show it holds for ##n+1## and done. You can define induction however you like, though. You may induce for all even or odd numbers. You may induce "backwards" [though that's not really correct way to say it.]

    What confused me is this bit: Show that for all ##n\geq 1## ##u_1<4##?? How exactly does ##u_1 ## quantify with respect to ##n##?
     
    Last edited: Apr 8, 2017
  8. Apr 8, 2017 #7
    Oh sorry that was a mistake.
    The question is:
    i. By considering##4−u_{n+1}##, prove by induction that ##u_n<4## for all ##n\geq1##
    Mod note: I have revised post #1 with this correction.
     
    Last edited by a moderator: Apr 8, 2017
  9. Apr 8, 2017 #8
    A series is an infinite sum. You are talking about a sequence. It's important to make the distinction or you will confuse people.

    The way I see it, your objective is to show by induction that for all ##n\in\mathbb{N}## ## u_n<4## and the base case is assumed to be solved according to your first post. Assume now that for some ##n>1 ## ##u_n<4## holds, then if you show ##4-u_{n+1}>0 ##, you will have proven the result.

    In #3, you solved the special case ##n=2 ##.
     
  10. Apr 8, 2017 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    In that last step, you are assuming that if ##\ u_1<4\ ## then ##\ \displaystyle 4-\frac{5+1}{1+1/2}>\frac{5+\frac{4}{u_1}}{1+\frac{2}{u_1}}\ ##.

    While that is true, you have not demonstrated this..
    I suggest picking up at your second line.
    ##\displaystyle\ 4-u_{2}=4- \frac{5u_1+4}{u_1+2}\ ##​
    Combine the two terms on the right hand side into one rational expression, using a common denominator. You can then show that ##\ u_2<4\ ## and that ##\ u_2>u_1\ ##, assuming that ##\ u_1>0\ ##.

    .
     
  11. Apr 8, 2017 #10
    Earlier you said, "While that is true, you have not demonstrated this.." Can you tell me what do you mean by this? How am I supposed to demonstrate that? The question already says that ##u_1<4## so can I not just continue by saying "Assuming inductive hypothesis to be true" and then divide by ##4## instead of ##u_1##

    $$\ 4-u_{2}=4-\frac{5u_1+4}{u_1+2} $$
    $$\ 4-u_{2}=\frac{4-u_1}{u_1+2} $$
    Considering ##u_n>0## then

    Now what I have to do?

    Edit:
    By the way, the question I typed is a little bit wrong
    Instead of proving ##u_1<4##, I have to prove ##u_n<4##
    Apologies.

    The ##5## in the numerator was incorrectly written. Changed it to the correct ##4##
     
    Last edited: Apr 8, 2017
  12. Apr 8, 2017 #11
    You have to use your inductive assumption. Also, when you simplify, you get ## 4-u_2 = \frac{3-u_1}{u_1+2}##
     
  13. Apr 8, 2017 #12
    So in the post where I proved for ##n=2##, if I were to substitute ##u_1## by ##u_n## and ##u_2## by ##u_{n+1}##, will the proof be valid?
     
  14. Apr 8, 2017 #13
    In any event for the special case, you could do something like this. Assume for a contradiction that ##4-u_2\leq 0 ##, then
    [tex]
    4-u_2 = \frac{4-u_1}{2+u_1} = 1-\frac{2-2u_1}{2+u_1}\leq 0
    [/tex]
    but then ##u_1\leq 0 ## which would contradict one of your assumptions in your first post. The general case follows similarly.
     
    Last edited: Apr 8, 2017
  15. Apr 8, 2017 #14

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    That looks good.

    ##u_1 \ ## is positive so ##\ u_1+2 \ ## is also positive, thus ## \ 4-u_2 >0 \ ##. Right ?

    You can also show that ##\ u_2>u_1 \ ## .
     
  16. Apr 8, 2017 #15
    It is actually ##4-u_1## in the numerator.
     
  17. Apr 8, 2017 #16
    Okay perfect. What I have to do next?
     
  18. Apr 8, 2017 #17
    Yes, you are right. I copied the problem incorrectly from your first post :( The core idea of my post is the same, regardless.

    Do the same for the general case. Assume ##4-u_n>0 ## for some ##n ## and show it must be true that ##4-u_{n+1}>0 ##.
     
  19. Apr 8, 2017 #18
    I have not studied principles for contradictions in depth so I am confused here. You assume ##4-u_2\leq 0 ##, a contradictory statement to be true. So any conclusions derived using this contradiction must be incorrect. So why are we treating the incorrect result to be a contradiction when it is itself an indirect proof that ##4-u_1\geq0##
     
  20. Apr 8, 2017 #19
    I have converted ##4-u_n>0 ## into ##\frac{24}{u_n+2}-u_{n+1}>0##
    I am not really sure what to do now. I know I can't use ##u_n=4## since that will make the left term smaller and the inequality might not hold true.
     
  21. Apr 8, 2017 #20
    When we have to prove ##A\Longrightarrow B ##, one possibility is to assume for a contradiction ##B## does not hold and consider ##A\land\neg B ##. If it yields a contradictory result, it means the assumption that ##\neg B ## must be incorrect. Due to the excluded third principle, it can then only be that ## B## is true. The contradictions you could arrive at could be ##A\land \neg B\Longrightarrow \neg A ##, which is clearly a contradiction. You could also contradict one of your assumptions or some base axioms.I will walk through the example in case of ##n=2##.

    Let ##4-u_1>0 ##. We want to show that
    [tex]
    4-u_1>0\Longrightarrow 4-u_2 = \frac{4-u_1}{2+u_1}>0
    [/tex]
    Let's assume for a contradiction that ##\frac{4-u_1}{2+u_1}\leq 0 ##. Then ##u_1\leq 0 ##, which contradicts the fact that all elements in the sequence are positive numbers.

    The validity of the statement is obvious, though and this sort of proof is overkill.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof by induction
  1. Induction Proofs (Replies: 3)

  2. Induction Proof (Replies: 11)

  3. Induction proof (Replies: 4)

  4. Proof by induction (Replies: 12)

  5. Proof by induction (Replies: 7)

Loading...