How to solve second degree recurrence relation?

Solution 1:

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.

Solution 2:

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*} $$

Solution 3:

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$.