0
$\begingroup$

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

Can anyone show me how to solve this? a and b are fixed, arbitrary integers. Does it mean I can put any value for a and b?

$\endgroup$
  • $\begingroup$ Does it mean I can put any value for a and b? It means that you need to find an expression for $f(n)$ in terms of $n$ and $a,b\,$. $\endgroup$ – dxiv May 22 '17 at 2:32
  • $\begingroup$ This is a homogeneous recurrence relation which you can solve as the Wikipedia link suggests. $\endgroup$ – Ross Millikan May 22 '17 at 2:35
1
$\begingroup$

The roots of $x^2-2x-1$ are $1\pm\sqrt{2}$. Hence, there exists $(\alpha,\beta)$ such that: $$f(n)=\alpha(1+\sqrt{2})^n+\beta(1-\sqrt{2})^n.$$ Using initial conditions, one has: $$a=\alpha+\beta,b=\alpha+\beta+(\alpha-\beta)\sqrt{2}.$$ Solving for $\alpha$ and $\beta$, one has: $$f(n)=\frac{b-a+a\sqrt{2}}{2\sqrt{2}}(1+\sqrt{2})^n+\frac{a-b+a\sqrt{2}}{2\sqrt{2}}(1-\sqrt{2})^n.$$

If you are wondering how I derived the closed form for $f(n)$, I have recently explained it there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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