# 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?

• 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\,$. – dxiv May 22 '17 at 2:32
• This is a homogeneous recurrence relation which you can solve as the Wikipedia link suggests. – Ross Millikan May 22 '17 at 2:35

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.

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