Solving the recurrence relations with boundary conditions

Question

This is the recurrence relation:

$$a_r - 4a_{r-1} + a_{r-2} = 1 + 2^r$$

and we have to solve this with boundary conditions $a_0 = 1$ and $a_1 = 2$.

I found the complementary solution, made the auxiliary equation and equated it to zero.

Can anyone help me with the particular solution and what I have to do with these boundary conditions?

Answer 1

With problems like this there are two rules that I like to follow. The first is to generalize the coefficients so that the solution is more useful, and second is to transform the equation to an easily solvable form. Here, that means transforming the non-homogeneous terms out.

Consider the recurrence

$$g_n=ag_{n-1}+bg_{n-2}+A+B^n$$

We know that most non-homogeneous solutions mimic the non-homogeneous terms, thus we assume that

$$g_n=f_n+p+qB^n$$

so that

$$ \begin{align} f_n+p+qB^n&=a(f_{n-1}+p+qB^{n-1})\\ &+\ b(f_{n-2}+p+qB^{n-2})\\ &+\ A+B^n \end{align} $$

Selecting $p=\frac{A}{1-a-b}$ and $q=\frac{A}{1-a/B-b/B^2}$ we arrive at the desired form, namely

$$f_n=af_{n-1}+bf_{n-2}$$

I have demonstrated a completely general solution to this recurrence that has been described previously here. The solution is given as

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{af_0}{2} \frac{\alpha^n+\beta^n}{\alpha+\beta}$$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$, and $f_0=g_0-p-q$ and $f_1=g_1-p-qB$

Now we can specialize to your own problem. Specifically, given $a=4,b=-1, A=1,\ \&\ B=2$, we find that $p=-1/2,\ q=-4/3,\ \alpha,\beta=2\pm\sqrt{3}$. And just so you know, I've checked all of this numerically, comparing the recurrence with the analytic solution so derived.

Answer 2

Let $A(z) = \sum_{r \ge 0} a_r z^r$ be the ordinary generating function. Multiply the recurrence by $z^r$ and sum to obtain $$\sum_{r \ge 2} (a_r - 4a_{r-1} + a_{r-2}) z^r = \sum_{r \ge 2}(1 + 2^r) z^r.$$ Equivalently, $$\sum_{r \ge 2} a_r z^r - 4z\sum_{r \ge 2}a_{r-1} z^{r-1} + z^2 \sum_{r \ge 2} a_{r-2} z^{r-2} = \sum_{r \ge 2} z^r + \sum_{r \ge 2} (2z)^r,$$ which can be rewritten as $$\left(A(z) - a_0 z^0 - a_1 z^1\right) - 4z \left(A(z)-a_0 z^0\right) + z^2 A(z) = \frac{z^2}{1-z} + \frac{(2z)^2}{1-2z}.$$ Substituting the initial conditions yields $$\left(A(z) - 1 - 2 z\right) - 4z \left(A(z)-1\right) + z^2 A(z) = \frac{z^2}{1-z} + \frac{4z^2}{1-2z}.$$ Solving for $A(z)$ yields \begin{align} A(z) &= \frac{1-2z+\frac{z^2}{1-z} + \frac{4z^2}{1-2z}}{1-4z+z^2} \\ &= \frac{1-5z+13z^2-10z^3}{(1-z)(1-2z)(2+\sqrt3-z)(2-\sqrt3-z)} \\ &= \frac{-1/2}{1-z} - \frac{4/3}{1-2z} + \frac{(17+\sqrt3)/12}{1-(2-\sqrt3)z} + \frac{(17-\sqrt3)/12}{1-(2+\sqrt3)z} \\ &= -\frac{1}{2}\sum_{r\ge 0}z^r - \frac{4}{3}\sum_{r\ge 0} (2z)^r + \frac{17+\sqrt3}{12}\sum_{r\ge 0}((2-\sqrt3)z)^r + \frac{17-\sqrt3}{12}\sum_{r\ge 0}((2+\sqrt3)z)^r \\ &= \sum_{r\ge 0}\left(-\frac{1}{2} - \frac{4}{3} 2^r + \frac{17+\sqrt3}{12}(2-\sqrt3)^r + \frac{17-\sqrt3}{12}(2+\sqrt3)^r\right)z^r, \end{align} which immediately implies that $$a_r = -\frac{1}{2} - \frac{4}{3} 2^r + \frac{17+\sqrt3}{12}(2-\sqrt3)^r + \frac{17-\sqrt3}{12}(2+\sqrt3)^r.$$