# Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$

Bring the following recursion relation to an explicit expression:

$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$ $a_{0} = 0$, $a_1 = 1$, $a_2 = 2$

All the examples I have seen were with maximum 2 steps back ($a_{n-2}$) and I thought I know how to solve those but I'm having a hard time both with the Generating function and the Characteristic polynomial methods.

The Generating function should start from $n = 3$ but what would happen to the defined values?

For the Characteristic polynomial, Does it mean I'll have to find the roots of a polynomial from a 3rd degree?

• Yes. If you know some linear algebra, you can also convert to a problem about $3\times 3$ matrices. Of course, you get the same third-degree polynomial to solve to find the eigenvalues. May 17 '13 at 20:20
• You also need to deal with that constant $8$. Have you seem examples of handling that? The methods are often analogous to handling non/homogeneous differential equations! May 17 '13 at 20:20
• Yeah @JyrkiLahtonen, I think I'm supposed to treat it as the non-homogeneous part of the expression by finding the roots of the non-homogeneous part of the expression. In second thought I'm not quite sure on how to do this either. May 17 '13 at 20:24
• You will find that the characteristic equation has $1$ as a root giving an arbitrart constant term to the solution of the homogeneous equation. Just like in the case of differential equation you fix that with an ansatz that is a linear polynomial - or a higher degree one, if $1$ is a multiple root :-). May 17 '13 at 20:59

If you use the characteristic polynomial, it will indeed be a cubic, but it’s a cubic that factors very easily: it’s

$$x^3-3x_2+3x-1=(x-1)^3\;.$$

If you use generating functions, note that you can write the recurrence as

$$a_n=3a_{n-1}-3a_{n-2}+a_{n-3}+8-8[n=0]-7[n=1]-9[n=2]\;,\tag{1}$$

valid for all $n\in\Bbb Z$ if you make the blanket assumption that $a_n=0$ for all $n<0$. The last three terms are Iverson brackets and are there to make the recurrence yield the correct initial values.

Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}a_nx^n=3\sum_{n\ge 0}a_{n-1}x^n-3\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}a_{n-3}x^n+8\sum_{n\ge 0}x^n-8-7x-9x^2\;.\tag{2}$$

If the generating function is $A(x)$, $(2)$ can be rewritten as

$$A(x)=3xA(x)-3x^2A(x)+x^3A(x)+\frac8{1-x}-8-7x-9x^2\;,$$

which you can then solve for $A(x)$ and resolve into partial fractions.

• how did you factor the cubic this fast? did you know the formula for $(a-b)^3$ or is there a technique? May 17 '13 at 20:33
• @Georgey: I recognized it: it’s just the alternating sign version of $x^3+3x^2+3x+1=(x+1)^3$, which is very nearly as familiar as $x^2+2x+1=(x+1)^2$. But yes, I do know that $$(a-b)^3=a^3-3a^2b+3ab^2-b^3\;.$$ May 17 '13 at 20:36
• Could you please explain briefly or direct me to somewhere I can read how to treat the non-homogeneous part? May 18 '13 at 8:49

To expand one of the comments, if $A_n$ is a solution of the homogeneous part $$A_n=3A_{n-1}-3A_{n-2}+A_{n-3}$$ and $B_n$ satisfies $$B_n=3B_{n-1}-3B_{n-2}+B_{n-3}+8$$ then $kA_n+B_n$ satisfies the original recurrence.

The characteristic polynomial of the homogeneous part is $(x-1)^3$. I have given some answers to questions similar in content going into a clunky form of why the following works - generating functions give the same answer, and a sound proof - $A_n=(pn^2+qn+r)1^n$ where $p, q, r$ are arbitrary, and I've emphasised $1^n (=1)$ because it would be $2^n$ if the generating function had a factor $(x-2)^3$, and it would be a cubic in $n$ if it were $(x-\alpha)^4$ (etc).

The difficulty then arises because the inhomogeneous part $8=8\times 1^n$, and $1$ is a solution of the characteristic polynomial, so the obvious test function $B_n=constant$ won't work. In fact, because $A_n$ involves a quadratic, it is the next highest power you test: $B_n=kn^3$ to find the value of $k$.

As I say, generating functions will get you there, as will other methods, if you want to prove the method works. On the other hand, if you want to identify a solution quickly, it is useful to know which functions to test. $A_n+B_n$ has three parameters $p, q, r$ which determine the sequence, and these correspond to the three values of $a_n$ which are required to do the same. So, given the initial values (or three values of $a_m$), it is easy to show that the solution is unique. The test functions I have suggested work, so they provide the solution.

Do try it out, because the theory all hangs together.

Rewrite the expression for simplicity as $$a_{k+3}=3 a_{k+2} -3 a_{k+1} +a_k +8$$ Multiply by $z^k$ and sum over $k$ to get the generating function $G(z)=\sum_{k \geq 0}a_k z^k$. On LHS you'll get $$\frac{1}{z^3}\bigg(G(z)-a_0 -a_1 z -a_2 z^2\bigg)$$ On RHS you get $$\frac{3}{z}\bigg(G(z)-a_0\bigg)-\frac{3}{z^2}\bigg(G(z)-a_0-a_1 z\bigg)+G(z)+\frac{8}{1-z}$$ Now do the algebra carefully to get on LHS $G(z)$ and on RHS some expression of the form $\sum_{k=0}^{\infty}\varphi_k z^k$. Can you handle from here?