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?

  • $\begingroup$ 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. $\endgroup$ May 17 '13 at 20:20
  • $\begingroup$ 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! $\endgroup$ May 17 '13 at 20:20
  • $\begingroup$ 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. $\endgroup$
    – Georgey
    May 17 '13 at 20:24
  • 1
    $\begingroup$ 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 :-). $\endgroup$ 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


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


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


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

  • $\begingroup$ how did you factor the cubic this fast? did you know the formula for $(a-b)^3$ or is there a technique? $\endgroup$
    – Georgey
    May 17 '13 at 20:33
  • 1
    $\begingroup$ @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\;.$$ $\endgroup$ May 17 '13 at 20:36
  • $\begingroup$ Could you please explain briefly or direct me to somewhere I can read how to treat the non-homogeneous part? $\endgroup$
    – Georgey
    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?


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.