How to calculate this limit, in terms of $a, b, k, ..$? $$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$
 A: 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 $$
