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

-
This recurrence is linear and second-order, not second-degree. – Brian M. Scott Dec 9 '12 at 9:33
@BrianM.Scott sorry, that whas what is written in my assignment paper... so I tried googling it. Also thank you for editing the post. It is my first time using this site. – NewProger Dec 9 '12 at 9:34
A better search term is homogeneous linear recurrence; with a bit of searching you’ll find a number of methods of solving this type of recurrence. (You’re welcome; your post was clear enough to be very easy to edit. You can find instruction here on how to produce mathematical symbols on the site. – Brian M. Scott Dec 9 '12 at 9:40
@BrianM.Scott, thank you again. I will do as you suggested. – NewProger Dec 9 '12 at 9:41
I’ve given a little more detail in my answer, perhaps enough to help you wade through a general treatment of this method, of which there are many online. – Brian M. Scott Dec 9 '12 at 9:59

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.

-
That's what I was trying to find :) Really appreciate your help! – NewProger Dec 9 '12 at 10:22
@NewProger: Oh, good; I’m glad it helped. – Brian M. Scott Dec 9 '12 at 10:22

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

-
Sorry, but I don't really get it :( Can you please provide a general algorythm or a link to some guide? – NewProger Dec 9 '12 at 9:40
It would be better to say that this is one standard way. – Brian M. Scott Dec 9 '12 at 9:41
this is exactly how you solve differential equations. This one is called a difference equation. Just google it. – dexter04 Dec 9 '12 at 9:42
@BrianM.Scott Agreed. Corrected. – dexter04 Dec 9 '12 at 9:43
You should check your $\alpha$ and $\beta$; if I’m not mistaken, you solved the system incorrectly. – Brian M. Scott Dec 9 '12 at 9:58

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

-