Given a_{n} = (n^{2} + 1) 3^{n}, find a recurrence relation a_{n} + p a_{n+1} + q a_{n+2} + r a_{n+3} = 0. Hence evaluate ∑_{n≥0} a_{n} x^{n}

**Solution**

Easy.

We can solve formally to get the recurrence relation, but it is quicker to get there informally. We look for a relation between b_{n} = a_{n}, b_{n+1} = a_{n+1}/3, b_{n+2 = }a_{n+2}/9, b_{n+3 = }a_{n+3}/27, because that takes care of the powers of 3. So, ignoring the 3^{n}, we are looking at:

n^{2} + 1

n^{2} + 2n + 2

n^{2} + 4n + 5

n^{2} + 6n + 10

We try to get a linear combination of the first three which is constant. But that is easy: subtracting twice the second from the third gets rid of the n term, then adding the first gets rid of the n^{2} term. So, b_{n+2} - 2b_{n+1} + b_{n} = 2.3^{n}. But b_{n+3} - 2b_{n+2} + b_{n+1} has the *same* value, so subtracting:

a_{n+3} - 9a_{n+2} + 27a_{n+1} - 27a_{n} = 0, which is the required recurrence relation.

Let the power series sum to y. Then taking y - 9x + 27x^{2}y - 27x^{3}y will give a_{n+3} - 9a_{n+2} + 27a_{n+1} - 27a_{n} as the coefficient of x^{n+3}, so we need only worry about the early terms: a_{0} + (a_{1} - 9a_{0})x + (a_{2} - 9a_{1} + 27a_{0})x^{2} = (1 - 3x + 18x^{2}). Hence y = (1 - 3x + 18x^{2})/(1 - 9x + 27x^{2} - 27x^{3}).

Using the ratio test, the original series evidently converges for |x| < 1/3, which may prompt us to notice that 1 - 9x + 27x^{2} - 27x^{3} = (1 - 3x)^{3}.

That in turn may prompt us to try solving the problem backwards. We know that:

1/(1 - z) = ∑ z^{n}; 1/(1 - z)^{2} = ∑ (n+1)z^{n}; 1/(1 - z)^{3} = ∑ (n+1)(n+2)/2 z^{n}.

Hence 2/(1 - z)^{3} - 3/(1 - z)^{2} + 2/(1 - z) = ∑ (n^{2} + 1)z^{n}. Replacing z by 3x gives ∑ a_{n} x^{n} = (1 - 3x + 18x^{2})/(1 - 3x)^{3}. Multiplying across by (1 - 3x)^{3} now gives the required recurrence relation.

© John Scholes

jscholes@kalva.demon.co.uk

4 Sep 1999