Solving recurrence relation. Recurrence

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?

Solution 1:

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.