2
$\begingroup$

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.

  • 1
    I’ve give$n$ 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.2012-12-09

3 Answers 3

2

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.

  • 0
    @NewProger: Oh, good; I’m glad it helped.2012-12-09
1

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

  • 0
    You should check your $\alpha$ and $\beta$; if I’m not mistaken, you solved the system incorrectly.2012-12-09
1

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