How to calculate this limit, in terms of $a, b, k, ..$?

Question

$$f(0) = a \\ f(n+1) = f(n) + f(n-1) \\ g(0) = b \\ g(n+1) = g(n) + g(n-1)$$ $$ \lim_{n \to \infty} {{f(n+k)} \over {g(n)}}$$ where $a, b, n, k \in \mathbb Z$

Answer 1

Denote $\phi = \frac{1+\sqrt{5}}{2}$, $\varphi = \frac{1-\sqrt{5}}{2} = 1-\phi = -\phi^{-1}$. We will prove that any sequence defined by

$$ x_n=R\phi^n + T\varphi^n $$

satisfies recurrence $x_{n+1}=x_n+x_{n-1}$. Then we will prove the reverse: our sequences $f(n)$, $g(n)$ have form $R\phi^n + T\varphi^n$ for some $R$, $T$. This is analogous to Binet formula for Fibonacci numbers.

Firstly, we'll check the recurrence. You can check that both $\phi$ and $\varphi$ satisfy equation $x^2+x+1=0$. Therefore

$$ x_{n+2} = R\phi^{n+2} + T\varphi^{n+2} = R\phi^n\phi^2 + T\varphi^n\varphi^2 = R\phi^n (\phi + 1) = T\varphi^n (\varphi+1) = R\phi^{n+1} + R\phi^n + T\varphi^{n+1} + T\varphi^n = x_{n+1}+x_n,$$

q.e.d. Any such sequence satisfies

$$ \lim_{n \to \infty} \frac{x_n}{\phi^n} = R, $$

as $|\varphi|<1$, so $\varphi^n \to 0$.

Now, if we will find such $R_f$, $T_f$, that $R_f\phi^0+T_f\varphi^0 = a$ and $R\phi^1 + T\varphi^1 = c$, then, inductively, $f(n) = R_f\phi^n + T_f\varphi^n$. Finding such $R_f$, $T_f$ is just a matter of solving a system of two linear equations. Analogically, we find $R_g$ and $T_g$.

Then, finally

$$ \lim_{n \to \infty} \frac{f(n+k)}{g(n)} = \lim_{n \to \infty} \frac{f(n+k)}{\phi^{n+k}} \cdot \frac{\phi^n}{g(n)} \cdot \phi^k = \frac{R_f}{R_g} \cdot \phi^k $$

I calculated $R_f$ to be $\frac{a\varphi-c}{\varphi-\phi}, so we can plug this values to get

$$ \lim_{n \to \infty} \frac{f(n+k)}{g(n)} = \frac{a\varphi-c}{b\varphi-d} \cdot \phi^k = \frac{c\phi+a}{d\phi+b} \cdot \phi^k $$