Given an = (n2 + 1) 3n, find a recurrence relation an + p an+1 + q an+2 + r an+3 = 0. Hence evaluate ∑n≥0 an xn
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 bn = an, bn+1 = an+1/3, bn+2 = an+2/9, bn+3 = an+3/27, because that takes care of the powers of 3. So, ignoring the 3n, we are looking at:
n2 + 1
n2 + 2n + 2
n2 + 4n + 5
n2 + 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 n2 term. So, bn+2 - 2bn+1 + bn = 2.3n. But bn+3 - 2bn+2 + bn+1 has the same value, so subtracting:
an+3 - 9an+2 + 27an+1 - 27an = 0, which is the required recurrence relation.
Let the power series sum to y. Then taking y - 9x + 27x2y - 27x3y will give an+3 - 9an+2 + 27an+1 - 27an as the coefficient of xn+3, so we need only worry about the early terms: a0 + (a1 - 9a0)x + (a2 - 9a1 + 27a0)x2 = (1 - 3x + 18x2). Hence y = (1 - 3x + 18x2)/(1 - 9x + 27x2 - 27x3).
Using the ratio test, the original series evidently converges for |x| < 1/3, which may prompt us to notice that 1 - 9x + 27x2 - 27x3 = (1 - 3x)3.
That in turn may prompt us to try solving the problem backwards. We know that:
1/(1 - z) = ∑ zn; 1/(1 - z)2 = ∑ (n+1)zn; 1/(1 - z)3 = ∑ (n+1)(n+2)/2 zn.
Hence 2/(1 - z)3 - 3/(1 - z)2 + 2/(1 - z) = ∑ (n2 + 1)zn. Replacing z by 3x gives ∑ an xn = (1 - 3x + 18x2)/(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