Results 1 to 3 of 3

Math Help - limits of recurrance relation, log(a+b)

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    2

    limits of recurrance relation, log(a+b)

    Hi, I am trying to solve the following limit:
    \lim_{k\to\infty} \frac{1}{k} \log N(k)
    where
    N(k) = N(k-1) + N(k-2)
    with provided initial conditions. I have solved the recurrence relationship, and the specific solution does contain two terms:
    N(k) = a_1 r_1^k + a_2 r_2^k
    I've tried a few tricks to simplify the log expression, including:
    \frac{1}{k}logN(k) = \frac{1}{k}\log\left(a_1 r_1^k\left(1 + \frac{a_2}{a_1}\left(\frac{r_2}{r_1}\right)^k \right) \right)  = \frac{1}{k}\log(a_1) + \log(r_1) + \log\left(1 + \frac{a_2}{a_1}\left(\frac{r_2}{r_1}\right)^k \right)
    and was able to modify this expression to bound the limit, but haven't been able to obtain the limit itself.

    I have also tried to compute the limit directly on the recurrence relationship (rather than solving it first) but ran into similar problems with log(A+B) terms. Any suggestions on how to proceed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2011
    Posts
    2

    Re: limits of recurrance relation, log(a+b)

    I forgot to mention, |r_i| > 1, so the limit does not go to zero. I also tried L'Hopital's rule (since this is an \infty/\infty form), to get:
    =\lim_{k\to\infty} \frac{\ln(r_1) a_1 r_1^k + \ln(r_2) a_2 r_2^k}{a_1 r_1^k + a_2 r_2^k}
    which is also in \infty/\infty form, and repeated application of L'Hopital's rule does not simplify the fraction.

    Edit: I'm stupid: one of the r_i is less than 1, and thus that term goes to zero, making the limit of the other term easy to find.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: limits of recurrance relation, log(a+b)

    Quote Originally Posted by pavon View Post
    Hi, I am trying to solve the following limit:
    \lim_{k\to\infty} \frac{1}{k} \log N(k)
    where
    N(k) = N(k-1) + N(k-2)
    with provided initial conditions. I have solved the recurrence relationship, and the specific solution does contain two terms:
    N(k) = a_1 r_1^k + a_2 r_2^k
    I've tried a few tricks to simplify the log expression, including:
    \frac{1}{k}logN(k) = \frac{1}{k}\log\left(a_1 r_1^k\left(1 + \frac{a_2}{a_1}\left(\frac{r_2}{r_1}\right)^k \right) \right)  = \frac{1}{k}\log(a_1) + \log(r_1) + \log\left(1 + \frac{a_2}{a_1}\left(\frac{r_2}{r_1}\right)^k \right)
    and was able to modify this expression to bound the limit, but haven't been able to obtain the limit itself.

    I have also tried to compute the limit directly on the recurrence relationship (rather than solving it first) but ran into similar problems with log(A+B) terms. Any suggestions on how to proceed?
    Suppose that r_1\geqslant r_2. Then a_1r_1^k \leqslant N(k) \leqslant (a_1+a_2)r_1^k. Use that to get \tfrac1k\log N(k) sandwiched between two quantities that tend to the same limit.

    Obviously if r_1<r_2 then you'll have to use r_2 instead of r_1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove recurrance relation
    Posted in the Differential Equations Forum
    Replies: 9
    Last Post: December 15th 2010, 04:52 PM
  2. Recurrance Relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 14th 2010, 10:52 PM
  3. recurrance relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2009, 05:33 PM
  4. Solving recurrance relation using any technique
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 1st 2008, 04:11 AM
  5. Finding Function for a recurrance relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 17th 2008, 03:46 PM

/mathhelpforum @mathhelpforum