Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
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 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
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. –  Brian M. Scott Dec 9 '12 at 9:59
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.