Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction/recusive sequences - just need a hint

  1. Sep 25, 2004 #1
    How do I prove by mathematical induction that the sequence given by

    [tex] a_{n+1}=3-\frac{1}{a_n} \qquad a_1=1 [/tex]

    is increasing?

    The difficulty in finding it myself is that recursive sequences are not familiar to me---i.e. usually, I am able do the following steps without a problem:

    (A) Show n=1 gives a true statement.
    (B) Assume it is true for n=k.
    (C) Get to n=k+1 and complete the proof.

    ... but this is not a regular sequence. Can anyone give me a tip?
  2. jcsd
  3. Sep 25, 2004 #2
    Not quite sure what kind of hint you're after... You wish to prove that a_(n + 1) > a_n for all n. The inductive step is basically showing that a_(k + 2) > a_(k + 1) if a_(k + 1) > a_k. If you work with the first inequality, you'll surely find something. Remember that you can relate a number in the sequence to its predecessor, e.g. a_(k + 2) = 3 - 1/a_(k + 1).
  4. Sep 25, 2004 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    At n=1, we find a(2)=2>1=a(1), that is, the first step is verified.

    Assume a(k)>a(k-1)
    Prove that a(k+1)>a(k):

    a(k+1)-a(k)=3-1/a(k)-(3-1/a(k-1))=1/a(k-1)-1/a(k)>0, since a(k)>a(k-1)
  5. Sep 25, 2004 #4
    Oh... I've got it. Thanks. :smile:
  6. Sep 25, 2004 #5
    have you shown n=1?also, how does your prof let you play with the equations, does he/she let you pretty much play with them any way that is algebraically sensical or do you have to take a more controlled approach like playing with one side only, etc.?
  7. Sep 26, 2004 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    What are you getting at?
    I've solely used the definitions of the term in the sequence; I haven't presupposed anything that should be proven :confused:
  8. Sep 28, 2004 #7
    to use induction, you show that it it true for n=1 before any other step is taken.
  9. Sep 28, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    erm, and he did show n=1 is ok, in fact that was the first sentence in his proof.
  10. Sep 28, 2004 #9
    Sorry for the late reply---I didn't notice my notification was set to weekly.

    Anyhow, I have simply shown what I intended to prove to be valid for:
    Then, it would be true for all n.

    Well, The difficulty I had has already been resolved with your assistance, guys.

    Thank you very much indeed. :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook