Results 1 to 3 of 3

Math Help - Help with a recursively defined sequence

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    1

    Help with a recursively defined sequence

    Hi,

    So my problem is as follows:

    I have a recursively defined sequence with a(1)=5, and a(n+1)=a(n)^2-a(n). The problem is to show that a(n)>2^2^n for all n>=1.

    Proof by Induction:

    Base: a(1) = 5 > 4 = 2^2^1, so it's true for n=1.

    Induction: a(n+1)=a(n)^2-a(n)>(2^2^n)^2-(2^2^n) and this is where I get stuck. Try as I might I can't seem to show that a(n+1)>2^2^(n+1).

    Any help will be much appreciated, and I'm not looking for a full solution just some hints would be great. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by LexMiguel View Post
    Hi,

    So my problem is as follows:

    I have a recursively defined sequence with a(1)=5, and a(n+1)=a(n)^2-a(n). The problem is to show that a(n)>2^2^n for all n>=1.

    Proof by Induction:

    Base: a(1) = 5 > 4 = 2^2^1, so it's true for n=1.
    Good. This part is right, however....

    Induction: a(n+1)=a(n)^2-a(n)>(2^2^n)^2-(2^2^n)
    This step is wrong. Note the negative sign does not preserve the inequality. So you cant say a(n)^2-a(n)>(2^{2^n})^2-2^{2^n}.

    I'm not looking for a full solution just some hints would be great. Thanks
    Observe that a(n+1) > a(n) ^2 = (2^{2^n})^2 = 2^{2^{n+1}}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Isomorphism View Post
    [snip]

    Observe that a(n+1) > a(n) ^2 = (2^{2^n})^2 = 2^{2^{n+1}}
    Isomorphism,

    I don't think that last line is right: it is not true that a(n+1) > a(n) ^2 .

    Here is an alternative approach. By the inductive hypothesis,

    a(n) > 2^{2^n}.

    Since a(n) is an integer,

    a(n) \geq 2^{2^n} + 1,

    so

    a(n+1) = a(n) \; [a(n) - 1] \geq (2^{2^n} + 1) [2^{2^n}] > (2^{2^n})^2 = 2^{2^{n+1}}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Limit of a recursively defined sequence
    Posted in the Calculus Forum
    Replies: 4
    Last Post: September 13th 2010, 04:33 AM
  2. Limit of a recursively defined sequence
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 10th 2009, 06:45 AM
  3. Recursively defined functions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 11th 2009, 05:23 PM
  4. Recursively defined functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 7th 2008, 10:12 AM
  5. Replies: 10
    Last Post: June 12th 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum