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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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.