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.

Given is a function $f(n)$ with:
$f(0) = 0$
$f(1) = 1$
$f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$

I was wondering if there's also a non-recursive way to describe the same function.

WolframAlpha tells me there is one:
$$g(n) = \frac{(\frac{1}{2}(3 + \sqrt{17}))^n - (\frac{1}{2}(3 - \sqrt{17}))^n}{\sqrt{17}}$$

However, I have absolutely no clue how to determine this function, especially the $\sqrt{17}$ makes no sense to me.

Could anyone maybe explain why $f(n)$ and $g(n)$ are the same?

share|improve this question
2  
Are you familiar with linear algebra, especially diagonalizing a matrix? –  Alex Becker Apr 16 at 21:05
    
You could just prove they are the same by induction. –  Git Gud Apr 16 at 21:20
    
Cool, so far 5 different ways to solve this (including the induction comment). I wonder how many different ways can be found. –  DanielV Apr 16 at 21:45
    
@AlexBecker I should be, but I feel like my knowledge about that didn't survive the semester holidays... :/ –  Christian Schnorr Apr 16 at 22:45
    
The $\sqrt{17}$ comes from $3^2+4 \times 2$, based on the coefficients of the recursion. In the Fibonacci sequence $f(n)=f(n-1)+f(n-2)$ you get $\sqrt{5}$ from $1^2+4 \times 1$ –  Henry Apr 17 at 13:20

5 Answers 5

up vote 15 down vote accepted

$$\begin{align} f(n) &= 3\,f(n-1) + 2\,f(n-2) \\ f(n-1) &= 1\,f(n-1) + 0\,f(n-2)\end{align}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n - 1) \\ f(n - 2) \end{bmatrix}$$

$$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n - 1} \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$$

$$\begin{bmatrix} f(n + 1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$

Diagonalize (find eigen values / eigen vectors) and you have your closed form.

$$\begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix} \begin{bmatrix} \frac{3 - \sqrt{17}}{2} & 0 \\ 0 & \frac{3 + \sqrt{17}}{2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac{2}{3 - \sqrt{17}} & \frac{2}{3 + \sqrt{17}} \end{bmatrix}^{-1} $$

share|improve this answer

You could prove that the formula is correct, by induction. It comes down to showing that the given expression satisfies the initial conditions and the recurrence.

There is also a general theory of homogeneous linear difference equations with constant coefficients. It says, for second-order difference equations (our case), that if the recurrence is $f(n)=pf(n-1)+qf(n-2)$, to do this.

1) Solve the equation $x^2-px-q=0$.

2) If the roots are distinct, say $\alpha$ and $\beta$, then the solutions of the difference equation are given by $$f(n)=A\alpha^n+B\beta^n.$$ The constants $A$ and $B$ can be determined by using the "initial values" $f(0)$ and $f(1)$.

share|improve this answer
    
Probably the (for me) easiest to understand answer! Thanks! –  Christian Schnorr Apr 16 at 22:43
    
You are welcome. –  André Nicolas Apr 16 at 22:47
    
This is brilliant. –  András Hummer Apr 17 at 9:08

This is called a linear recurrence. Solving them is fairly straightforward, and is explained here: http://en.wikipedia.org/wiki/Linear_recurrence#Solving.

The key thing to note is that if $f_1$ and $f_2$ are solutions of this recurrence, then $f_1 + f_2$ is as well (except for the initial conditions).

The trick is to assume that there is a solution of the form $f = cr^n$, and see where that leads you.

Let's see how it works out: $f(n) = 3f(n-1) + 2f(n-2)$\

$cr^n = 3cr^{n-1} + 2cr^{n-2}$

Dividing everything by $cr^{n-2}$ and rearranging gives: $r^2 - 3r - 2 = 0$. Factor, to get: $\frac{-1}{4} \left(-2 r+\sqrt{17}+3\right) \left(2 r+\sqrt{17}-3\right) = 0$

I conclude that $r = r_1 = \frac{\sqrt{17}-3}{2}$, or $r = r_2 = \frac{-\sqrt{17}+3}{2}$.

Using the fact that I can add solutions together and still have a solution to the recurrence relation, I'll write: $f(n) = c_1r_1^n + c_2r_2^n$

From here, you can plug in the initial conditions to solve for $c_1$ and $c_2$.

share|improve this answer

Use generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, write the recursion as: $$ f(n + 2) = 3 f(n + 1) + 2 f(n) $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ \frac{F(z) - f(0) - f(1) z}{z^2} = 3 \frac{F(z) - f(0)}{z} + 2 F(z) $$ With the initial values you get: $$ F(z) = \frac{z}{1 - 3 z - 2 z^2} $$ Split into partial fractions, and read off the coefficients by using geometric series.

share|improve this answer

There are multiple methods available, see also this wikipedia page.

Generating function Generally speaking, the method of generating functions is very powerful and allows you to solve many recurrent relations. However, the method is a bit abstract and requires a lot of error-prone calculations, so for a simple (homogenous) recurrent relation you probably want something simpler.

The method of undetermined coefficients
In which we assume a solution of the form $c^n$. This leads to a quadratic equation for which we hopefully can find two different solutions so that we can make a linear combination of the two that satisfies the boundary conditions. If there only one solution (with multiplicity 2) of the quadratic equation, you have to use the fact that the derivative of the quadratic is 0 as well (I don't remember the specifics, but it's not really relevant now, I just want to point out that this method doesn't always work).

The method of eigenvalues
This works as follows: write the recurrence relation in matrix form, and find the eigenvalues and eigenvectors of the matrix. When we've found them, we can hopefully write the initial conditions as a linear combination of eigenvectors. Now we can deduce the solution to the recurrence relatio. Suppose the initial conditions is $x_0 = av_1 + bv_2$ and $\lambda_1, \lambda_2$ are the eigenvalues of $v_1, v_2$. Then the solution to the recurrent relation is $x_n = a\lambda_1^nv_1 + b\lambda_2^nv_2$.

The method of undetermined coefficients is probably the easiest one to use.

share|improve this answer

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.