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.
 A: Associated with the recurrence $f(n)=-3f(n-1)+4f(n-2)$ is a so-called characteristic equation, $x^2=-3x+4$. Its coefficients are the same as the coefficients of the recurrence, and the powers of $x$ are chosen so that the smallest exponent is $0$, associated with the smallest argument of $f$, which in this case is $n-2$; the exponents then increase in step with the arguments of $f$, so that exponent $1$ goes with $(n-2)+1=n-1$, and exponent $2$ goes with $(n-2)+2=n$.
Now solve the auxiliary equation: $x^2+3x-4=0$, $(x+4)(x-1)=0$, $x=-4$ or $x=1$.
There is a general theorem that says that when the roots are distinct, as they are here, the general solution to the recurrence has the form
$$f(n)=Ar_1^n+Br_2^n\;,$$ where $r_1$ and $r_2$ are the two roots. Thus, for this recurrence the general solution is $$f(n)=A(-4)^n+B\cdot1^n=A(-4)^n+B\;.\tag{1}$$
$(1)$ gives all solutions to the recurrence $f(n)=-3f(n-1)+4f(n-2)$, for all possible initial values of $f(1)$ and $f(2)$. To determine which values of $A$ and $B$ correspond to your particular initial values, substitute $n=1$ and $n=2$ into $(1)$. For $n=1$ you get $$1=f(1)=A(-4)+B\;,$$ and for $n=2$ you get $$2=f(2)=A(-4)^2+B\;.$$
Now you have a system of two equations in two unknowns,
$$\left\{\begin{align*}
-4A+B&=1\\
16A+B&=2\;.
\end{align*}\right.$$
Solve this system for $A$ and $B$, substitute these values into $(1)$, and you have your general solution. (I get $A=\frac1{20}$ and $B=\frac65$.)
Note that if the the roots $r_1$ and $r_2$ of the characteristic equation are equal, say $r_1=r_2=r$, the general solution is a little different:
$$f(n)=Ar^n+Bnr^n\;.$$ However, you solve for the particular $A$ and $B$ in the same way.
A: 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*}
$$
A: A possible way is to assume a solution of the form $f(n) = A^n$ for some $A$ and use substitution to find out $A$. This is very similar to solving linear differential equations.
In your case,
$$A^n = -3A^{n-1} + 4A^{n-2}, n>2$$
Assuming $A\neq0$
$$A^2 + 3A-4 = 0$$
So, $A = -4,1$
So, $f(n) = \alpha(-4)^n+\beta(1)^n$
Now, plug in the initial values for $n= 1,2$ to get $\alpha ,\beta$.
