A particular linear recurrence relation

Question

I was trying to solve a recurrence relation: $$a_{n} = a_{n-1} - a_{n-2} + 1$$ The initial conditions are $a_0 = 1$, $a_1 = 2$. It looks very simple, but I only know the basic method of solving homogeneous relations with characteristic equations (doesn't apply here I guess) and also the method of using generating functions. I applied the latter and got a function that I wasn't able to expand into a power series, namely: $$f(x) = \frac{1}{(1-x)(1-x+x^2)}.$$ I've put it into Wolfram Alpha and got a simple sequence that loops after a few terms. I'm interested if the generating function approach can be continued somehow (can the function be expanded into a usable power series without very complicated techniques?). Also if there is another method good in a case like this one (I assume there is; are there any fairly simple ones, what's the "best" one?).

Answer 1

A really simple/naive way to solve the recurrence is to evaluate successive terms until you see periodicity:

$$\begin{align} a_2 &= 2-1+1 = 2 \\ a_3 &= 2-2+1 = 1 \\ a_4 &= 1-2+1 = 0 \\ a_5 &= 0-1+1 = 0 \\ a_6 &= 0-0+1 = 1 \\ a_7 &= 1-0+1 = 2 \end{align}$$ and here we stop because $a_6 = a_0$ and $a_7 = a_1$, and since the recurrence only uses two of the previous terms, we know that $a_{n+6} = a_n$ for all $n$. Then we can express $a_n$ as a case-wise function, or we can use trigonometric functions; e.g., $$a_n = 1 + \frac{2}{\sqrt{3}} \sin \frac{n\pi}{3}. \tag{1}$$

Now, if you wanted to get $(1)$ through a generating function, we would take your function and do a partial fraction decomposition:

$$f(x) = \frac{1}{1-x} + \frac{x}{1-x+x^2}. \tag{2}$$ The first term is just your usual geometric series, but the second is probably where you got stuck. We can use a trick: factor over the roots even if they are not rational or real:

$$x^2-x+1 = (x-r_1)(x-r_2), \quad r_1 = \frac{1}{2} + \frac{\sqrt{3}}{2} i, \quad r_2 = \frac{1}{2} - \frac{\sqrt{3}}{2} i. \tag{3}$$

Then partial fraction decomposition yields $$\frac{x}{1-x+x^2} = \frac{1}{r_1 - r_2} \left(\frac{r_1}{x-r_1} - \frac{r_2}{x-r_2}\right). \tag{4}$$

This means $$f(x) = \frac{1}{1-x} - \frac{1}{r_1-r_2} \left( \frac{1}{1-x/r_1} - \frac{1}{1-x/r_2}\right). \tag{5}$$

Now we can write this as the series expansion $$f(x) = \sum_{k=0}^\infty \left(1 + \frac{r_2^{-k} - r_1^{-k}}{r_1 - r_2}\right)x^k. \tag{6}$$ This immediately yields $$a_k = 1 + \frac{r_2^{-k} - r_1^{-k}}{r_1 - r_2}. \tag{7}$$ Now substitute back and simplify, observing that $$r_1 = e^{i \pi/3}, \quad r_2 = e^{-i \pi/3},$$ hence $$\frac{r_2^{-k} - r_1^{-k}}{r_1 - r_2} = \frac{e^{i \pi k/3} - e^{-i \pi k/3}}{i \sqrt{3}} = \frac{2}{\sqrt{3}} \frac{e^{i \pi k/3} - e^{-i \pi k/3}}{2i} = \frac{2}{\sqrt{3}} \sin \frac{k \pi}{3}. \tag{8}$$ This proves $(1)$ using the generating function method.

Answer 2

Sometimes there's a change of variables that converts it into a homogeneous recurrence. In this case, if we define $b_n = a_n - 1$ so that $a_n = b_n + 1$ for each $n \in \mathbb{N}$, then \begin{align} b_n &= a_n - 1 \\ &= a_{n-1} - a_{n-2} \\ &= (b_{n-1} + 1) - (b_{n-2} + 1) \\ &= b_{n-1} - b_{n-2}. \end{align}

This is simpler to analyze, using whatever method you like, and the resulting formula for $b_n$ can easily be converted back into a formula for $a_n$.

---

Challenge question: In this context, where $b_n = a_n - k$ for some constant $k$, what is the relationship between the ordinary generating functions?

Answer 3

Here is an alternative method. Let $X_n = \begin{pmatrix}a_{n-1} \\a_n\end{pmatrix}$. One has $$X_n = \begin{pmatrix}0 & 1 \\ -1 & 1\end{pmatrix} X_{n-1} + \begin{pmatrix} 0 \\ 1\end{pmatrix} \tag{*}$$

Let $A= \begin{pmatrix}0 & 1 \\ -1 & 1\end{pmatrix}$ and $Y=\begin{pmatrix} 0 \\ 1\end{pmatrix}$. The relation $(\ast)$ easily solves as $$X_n = A^{n-1}(X_1-R)+R$$

where $R=(I-A)^{-1}Y$. This gives $R = \begin{pmatrix} 1 \\ 1\end{pmatrix}$, so $$X_n = A^{n-1}\begin{pmatrix} 0 \\ 1\end{pmatrix}+\begin{pmatrix} 1 \\ 1\end{pmatrix}.$$

Since $A^3=-I_2$, the powers of $A$ can easily be computed, and hence you get an explicit formula for $X_n$, and then for $a_n$.

Answer 4

$$a_{n} = a_{n-1} - a_{n-2} + 1$$ $a_0 = 1$, $a_1 = 2$

Solving the relation's homogeneous part and finding it's particular solution

---

$$a_n=a_n^h+a_n^p$$ For non-homogeneous recurrence relations, the closed form is a sum of its homogeneous solution and its particular solution; $$a_n^h\implies a_n=a_{n-1}-a_{n-2}=0$$

$$r^2-r+1=0 \implies r_1=-\omega ,r_2=-\omega^2$$

$$a_n^h=c_1(-\omega)^n+c_2(-\omega^2)^n\tag1$$

$$a_n^p\implies p_0=a_n=a_{n-1}=a_{n-2}$$

$$p_0 = p_0 - p_0 + 1\implies p_0=1=a_n^p\tag2$$

$$\boxed{a_n=c_1(-\omega)^n+c_2(-\omega^2)^n+1}$$

use the initial conditions and you shall get the closed form.

---

Note:

(1) $\omega=\frac{-1+i\sqrt3}{2}$, $\omega^2=\frac{-1-i\sqrt3}{2}$

(2) $c_1,c_2$ are constants

(3) More about Non-Homogeneous recurrence relation

Answer 5

Since it hasn't been mentioned, here's the fastest way to turn this equation homogeneous by hand: just linear combine offset recurrence equations to cancel out the inhomogeneous part.

Take the equations $a_n = a_{n-1} - a_{n-2} + 1$ and $a_{n-1} = a_{n-2} - a_{n-3} + 1.$ Simply subtract these two equations from one another to obtain a homogeneous recurrence relation.

This technique also works on factors depending on n, where you might occasionally have to use more offset copies of the inhomogeneous recurrence. For example, the recurrence $a_n = a_{n-1} + 5a_{n-2} + 3n + 5^nn^2 - 7$ can be turned homogeneous with the same technique. The factors you need to use to combine the offset recurrences are exactly those of the linear recurrence describing the inhomogeneous part $b_n = 3n + 5^nn^2 - 7$. In effect, the characteristic polynomial of the full recurrence will be the product of the homogeneous part's characteristic polynomial and the inhomogeneous part's characteristic polynomial.