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
    This recurrence is linear and second-**order**, not second-degree.2012-12-09
  • 0
    @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.2012-12-09
  • 1
    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](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) on how to produce mathematical symbols on the site.2012-12-09
  • 0
    @BrianM.Scott, thank you again. I will do as you suggested.2012-12-09
  • 1
    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.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
    That's what I was trying to find :) Really appreciate your help!2012-12-09
  • 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
    Sorry, but I don't really get it :( Can you please provide a general algorythm or a link to some guide?2012-12-09
  • 0
    It would be better to say that this is **one** standard way.2012-12-09
  • 0
    this is exactly how you solve differential equations. This one is called a difference equation. Just google it.2012-12-09
  • 0
    @BrianM.Scott Agreed. Corrected.2012-12-09
  • 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*} $$