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

1. ## 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?

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.

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

Originally Posted by pavon
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 then you'll have to use $r_2$ instead of $r_1.$