Solving recurrence relation. Recurrence

Question

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?

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

Answer 2

General technique is to use generating functions. Define:

$\begin{equation*} F(z) = \sum_{n \ge 0} f(n) z^n \end{equation*}$

Shift to get rid of substractions in indices, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} f(n + 2) z^n &= 2 \sum_{n \ge 0} f(n + 1) z^n + \sum_{n \ge 0} f(n) z^n \\ \frac{F(z) - f(0) - f(1) z}{z^2} &= 2 \frac{F(z) - f(0)}{z} + F(z) \\ \frac{F(z) - a - b z}{z^2} &= 2 \frac{F(z) - a}{z} + F(z) \end{align*}$

Solve for $F(z)$, write as partial fractions:

$\begin{equation*} F(z) = -{{\left(\sqrt{2}+1\right)\,b+\left(-2^{{{3}\over{2}}}-3\right)\,a }\over{2^{{{3}\over{2}}}\,\left(z+\sqrt{2}+1\right)}}-{{\left(\sqrt{ 2}-1\right)\,b+\left(3-2^{{{3}\over{2}}}\right)\,a}\over{2^{{{3 }\over{2}}}\,\left(z-\sqrt{2}+1\right)}} \end{equation*}$

If you have a term $(1 - \alpha z)^{-1}$ in the partial fraction decomposition, if gives rise to a term $\alpha^n$ in the solution. Other typical terms are:

$\begin{align*} (1 - \alpha z)^{-m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} (\alpha z)^n \\ &= \sum_{n \ge 0} \binom{m + n - 1}{m - 1} (\alpha z)^n \end{align*}$

giving rise to to a polynomial in $n$ multiplying $\alpha^n$.