<s>[INST] How to solve second degree recurrence relation? For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$.
But how do you solve second degree?
For example
$$f(n)=\begin{cases}
1,&\text{for }n=1\\
2,&\text{for }n=2\\
-3f(n-1)+4f(n-2),&\text{for }n>2\;.
\end{cases}$$
I tried googling "How to solve second degree recurrence relation?" but it gave me solutions only for first degree and some other random stuff.
 [/INST] Or use generating functions. Rewite the recurrence as:
$$
f(n + 2) = - 3 f(n + 1) + 4 f(n) \qquad f(1) = 1, f(2) = 2
$$
Define:
$$
F(z) = \sum_{n \ge 0} f(n + 1) z^n
$$
By the properties of ordinary generating functions (see e.g. Wilf's "generatingfunctionology"):
$$
\frac{F(z) - f(1) - f(2) z}{z^2} = - 3 \frac{F(z) - f(1)}{z} + 4 F(z)
$$
My own tame computer algebra system gives:
$$
F(z) = \frac{6}{5} \cdot \frac{1}{1 - z} + \frac{1}{5} \cdot \frac{1}{1 + 4 z}
$$
This expands as two geometric series:
$$
\begin{align*}
f(n) &= \frac{6}{5} + \frac{1}{5} (-4)^{n - 1} \\
     &= \frac{6}{5} - \frac{(-4)^n}{20}
\end{align*}
$$
</s>