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!

Proving a sequence (defined recursively) is monotonically decreasing

  1. Apr 27, 2015 #1
    1. The problem statement, all variables and given/known data
    A sequence (an) of real numbers is defined by a(1) = 6, a(n) = (1/4)(2*a(n−1) − 3) for n >= 2. where n is a natural number

    show the sequence is monotonically decreasing
    2. Relevant equations
    None

    3. The attempt at a solution

    I tried to prove it by induction.
    Let P(n) be the predicate that a(n) < a(n-1)


    base case

    p(2)...

    a(1) = 6
    a(2) = (1/4)*(2*6-3) = 9/4
    a(2) < a(1) ..... base case is true

    induction step

    assume p(k) to be true

    a(k) < a(k-1)

    now we try to prove p(k+1) is true using or assumption about p(k)

    a(k+1) = (1/4)*(2(k) - 3)

    rearranging

    a(k) = 2*a(k+1) - 3

    using our assumption

    a(k-1) < 2*a(k+1) - 3

    I'm not sure where to go from here I can't think of anyway of relating a(k) and a(k+1) with an inequality.
    any help would be appreciated.
     
  2. jcsd
  3. Apr 27, 2015 #2

    pasmith

    User Avatar
    Homework Helper

    Consider the recurrence [itex]b_n = \frac12 b_{n-1}[/itex] with [itex]b_1 > 0[/itex]. Is that sequence monotonic decreasing?

    Unfortunately your recurrence [itex]a_n = \frac12 a_{n-1} - \frac34[/itex] has an extra term on the right, but a linear change of variable to [itex]b_n = a_n + C[/itex] for some constant [itex]C[/itex] should remove it.
     
  4. Apr 27, 2015 #3
    so if we go back to a(k+1) = a(k)/2 - 3/4

    let b(n) = a(k) - 3/2

    so that a(k+1) = (1/2)*b(n)

    b(n) is greater than a(k+1)

    i.e.
    a(k)/2 - 3/4 > a(k+1)

    so I've got the an inequality in terms of the two terms of the sequence I need

    rearranging

    a(k) - 2a(k+1) > 3/2

    i.e a(k) > 2a(k+1)

    a(k+1) is positive

    so a(k) > a(k+1)

    would this be correct?
     
    Last edited: Apr 27, 2015
  5. Apr 27, 2015 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I think you mean b(k) = a(k)-3/2, and the next line should be a recurrence relation on the b's, no a terms in sight.
     
  6. Apr 27, 2015 #5
    I tried getting rid of the a's

    b(k) = a(k)-3/2

    b(k+1) = a(k+1) - 3/2

    b(k+1) = (1/4)(2*a(k) -3) -3/2

    b(k+1) = (1/2)*b(n) -3/2

    I've got a recurrence relation in b now but I'm not sure where to go from here other than saying

    2*b(k+1) = b(n) -3

    b(n) - 2*b(k+1) = 3
     
  7. Apr 28, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You've chosen the wrong C. Start again, substituting bn-C for an everywhere in the recurrence relation for an (being careful not switch between k and n this time) and post the equation you get for the b sequence (with C still in it).
     
  8. Apr 28, 2015 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I don't see any good reason to introduce this new "b" sequence. To show that a sequence is increasing, it is enough to show that [itex]a_{n+1}- a_n> 0[/itex].
     
    Last edited by a moderator: Apr 28, 2015
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: Proving a sequence (defined recursively) is monotonically decreasing
Loading...