1

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.

msteve
  • 6,068
Hyune
  • 101

3 Answers3

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

Leucippus
  • 26,329
  • Similiar to what Claude put above, I guess though it is just something I should remember when coming across any difference equation. Would this method work if instead the negative were a positive sign? – Hyune Mar 17 '15 at 04:19
  • 1
    The method would work the same for the difference equation $f_{n+2} = 3 f_{n+1} + 2 f_{n}$ with $f_{0} = 0, f(1) = 1$ the solution would then be \begin{align} f_{n} = \frac{1}{\sqrt{17}} \left[ \left( \frac{3 + \sqrt{17}}{2}\right)^{n} + \left( \frac{3 - \sqrt{17}}{2} \right)^{n} \right] \end{align} – Leucippus Mar 17 '15 at 04:25
2

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

Claude Leibovici
  • 260,315
  • It's actually my first time coming across recurrence equation, I can see what your doing, without any in-depth understanding of how the method came about. I guess I shall remember this method for whenever I come across a recursion equation such as this – Hyune Mar 17 '15 at 04:17
  • 1
    Have a look at http://www.wikihow.com/Solve-Recurrence-Relations – Claude Leibovici Mar 17 '15 at 04:25
  • Given that f(n)=4f(n-1)-4f(n-2) and given that f(0)=3, f(1)=10, what is f(8)?

    So I am having problems finding the recurrence equation on this one mainly because when I solve the characteristic polynomial I get roots of just r = 2.

    So when it comes to applying the conditions I am stuck trying to find out what c1 and c2 are for my recurrence equation.. Any ideas how I might solve this?

     – Hyune Mar 17 '15 at 04:44
  • In such a case of root multiplicity, you should have $f(n)=c_1 2^n+c_2 2^n n$. May I confess that I am very surprized you did not cover this topic ? – Claude Leibovici Mar 17 '15 at 04:52
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?

meta_warrior
  • 3,288
  • 18
  • 34