Results 1 to 5 of 5

Math Help - Integers sequence

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    91

    Integers sequence

    Show that the sequence of positive integers given by a_{2n} = 3a_n -1, \ \ a_{2n+1}=3a_n +1 is strictly increasing.
    I have written down a reductio-ad-absurdum-proof, but it's based largely on tedious reduction of indices in a and eventually showing that the argument is proved by the contradiction 1\geq 2, and now I'm not all that sure it is correct. Do you have any better ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    Maybe you can use an "explicit" form of (a_n) showing by induction that,

    given a_0

    for every p integer

    from n=2^p to 2^{p+1}-1,

    a_n = 3^{p+1} a_0 + \alpha_n where (\alpha_n) is a strictly increasing sequence of positive integers
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    91
    Quote Originally Posted by running-gag View Post
    Hi

    Maybe you can use an "explicit" form of (a_n) showing by induction that,

    given a_0

    for every p integer

    from n=2^p to 2^{p+1}-1,

    a_n = 3^{p+1} a_0 + \alpha_n where (\alpha_n) is a strictly increasing sequence of positive integers
    Hm... I'm not getting the induction thing at all... could you please explain it further?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by atreyyu View Post
    Hm... I'm not getting the induction thing at all... could you please explain it further?
    If you calculate the first few terms of the sequence in terms of a_1, you get

    (for n = 2 to 3)
    a_2 = 3a_1 - 1
    a_3 = 3a_1 + 1

    (for n = 4 to 7)
    a_4 = 9a_1 - 4
    a_5 = 9a_1 - 2
    a_6 = 9a_1 + 2
    a_7 = 9a_1 + 4

    and so on.

    The idea is to show that the subsequence a_p, ..., a_q where p = 2^n and q = 2^{n+1} - 1 is strictly increasing, because each term of this subsequence can be written as 3^na_1 + \alpha, and the \alpha are strictly increasing.

    You also need to show that for each n, a_x < a_y, where x = 2^n - 1 and y = 2^n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    91
    Ok, I decided to state that a is composed of subsequences c_k, where c_k=a_{2^k},a_{2^k+1},a_{2^k+2},\ldots,a_{2^{k+1}-1}, and now I want to show that every subsequence c_k, as well as that the last element of c_k is less than the first element of c_{k+1} so that there is an increase in the "boundary" when the coefficient by a_0 changes --and that's what I have most problems with. Could you help me out?
    Last edited by atreyyu; March 13th 2010 at 03:40 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: August 3rd 2010, 01:31 PM
  2. Replies: 0
    Last Post: July 4th 2010, 12:05 PM
  3. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 19th 2010, 02:02 PM
  4. Replies: 4
    Last Post: February 24th 2008, 03:08 PM
  5. Replies: 2
    Last Post: October 14th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum