Given that $f(n)=3f(n-1)-2f(n-2)$ for $n>1$ and given that $f(0)=0$, $f(1)=1$, what is $f(10)$?

Question

I understand how to work out this question using brute force (manually substituting the numbers in) was just wondering if there was a faster and less tedious way of doing this question.

Answer 1

First, you need to write out the first few terms, $f(0)=0$, $f(1)=1$, $f(2)=3$, $f(3)=7$,...

Now can you spot a pattern among the terms?

Answer 2

A classic method of solving the difference equation is of the following way. Consider the difference equation in the form $f_{n+2} = 3 f_{n+1} - 2 f_{n}$ and try a solution of the form $f_{n} = r^{n}$. This leads to the quadratic equation $r^{2} - 3 r + 2 = 0$ and has solutions $r = 2, 1$. From this it is then seen that $f_{n} = a \, 2^{n} + b \, 1^{n}$. From the condition $f_{0}= 0$ leads to $b= -a$. From the condition $f_{1} = 1$ leads to $a = 1$ for which $f_{n} = 2^{n} -1$. Now for $n=10$ the value becomes $f_{10} = 2^{10}-1 = 1023$.

Answer 3

You must proceed the usual way for finding a recurrence equation. I shall remember you what you already know.

For your equation, the characteristic polynomial is $r^2=3r-2$ the roots of which being $r_1=1$ and $r_2=2$. So, before using the conditions, we know that the general solution is $$f(n)=c_1 1^n+c_2 2^n=c_1+c_2 2^n$$ Applying the conditions, we than have $f(0)=c_1+c_2=0$, $f(1)=c1+2c_2=1$ from which $c_1=-1,c_2=1$. This makes $$f(n)=-1+2^n$$