0

Solve the recurrence relation
$$f(n) = 2f(n - 1) + f(n - 2)$$ with initial conditions $f(0) = a, f(1) = b$. (here a and b are fixed, arbitrary integers).

I'm confused on how to approach this, a and b are fixed, arbitrary integers.

M.Jones
  • 357
  • I don't understand your answer in that , wouldn't we create a characteristic equation first ? – M.Jones May 24 '17 at 02:01
  • 1
    This is what I have down, this the polynomial $x^2-2x-1$. – C. Falcon May 24 '17 at 02:02
  • wouldn't it be 2x^2 instead of x^2 because we have 2f(n-1) – M.Jones May 24 '17 at 02:03
  • The $2$ is in front of $x$. Since we have a second order linear recurrence relation, the term with the biggest index is associated with $x^2$, the second biggest index with $x$ and the least one with $1$. Indeed, notice that: $$\begin{pmatrix}f_{n-1}\f_{n}\end{pmatrix}=\begin{pmatrix}0&1\1&2\end{pmatrix}\begin{pmatrix}f_{n-2}\f_{n-1}\end{pmatrix}.$$ What is the characteristic polynomial of the square matrix? – C. Falcon May 24 '17 at 02:13
  • hmm never done characteristic equations with matrix so couldn't tell you :/ – M.Jones May 24 '17 at 02:14
  • 1
    Then, I can only recommend you to read carefully your course notes and rehearse the method for solving such equations. The matrix trick is only used to make the proof. Alternatively, you can show that the set of solutions is a $2$-dimensional vector space and search for a solution of the form $r^{n},r^{-n}$, you will find and equation for $r$, which is $r^2-2r-1=0$. – C. Falcon May 24 '17 at 02:20
  • Let us continue this discussion in chat. – M.Jones May 24 '17 at 02:37

1 Answers1

1

We solve first the characteristic equation of the difference equation, which is: $$ r^2 = 2r + 1 $$ resulting in solutions: $$ r_1 = 1+\sqrt{2} \qquad r_2= 1-\sqrt{2} $$ The general solution to the difference equation is then: $$ f(n)= c_1 (1+\sqrt{2})^n + c_2 (1-\sqrt{2})^n $$ Solving for the two coefficients, we use the initial conditions: \begin{align*} f(0) &= a & f(1) &= b \\ c_1+c_2 &= a & (1+\sqrt{2})c_1 + (1-\sqrt{2})c_2 &= b \end{align*} $$ c_1 = \frac{(2-\sqrt{2})a + \sqrt{2} \, b}{4} \qquad c_2 = \frac{(2+\sqrt{2})a - \sqrt{2} \, b}{4} $$ So the difference equation with initial conditions: $$ f(n) = 2 f(n-1) + f(n-2) \quad\qquad f(0)=a, f(1) = b $$ has solution: $$ f(n) = \left( \frac{(2-\sqrt{2})a + \sqrt{2} \, b}{4} \right) (1+\sqrt{2})^n + \left( \frac{(2+\sqrt{2})a - \sqrt{2} \, b}{4} \right) (1-\sqrt{2})^n $$

Manuel Guillen
  • 2,703