Combinatorics

The generating function for this sequence is \(a(x)=\sum_{i=0}^\infty a_i x^i\text{.}\)

Now, we are going to use the recursive relation. We know that \(a_n=3a_{n-1}-1\text{,}\) or, by rearranging this, \(a_n-3a_{n-1}=-1\text{.}\) Thus, if we could get the coefficient of \(x^n\) to look like \(a_n-3a_{n-1}\text{,}\) we could use the recursive relation to replace this by \(-1\text{.}\) Right now, the coefficient of \(x^n\) is \(a_n\text{,}\) and the only place \(a_{n-1}\) shows up is as the coefficient of \(x^{n-1}\text{.}\) But if we multiply \(a(x)\) by \(x\text{,}\) then \(a_{n-1}x^{n-1}\) becomes \(a_{n-1}x^n\text{,}\) so if we also multiply by \(-3\text{,}\) we get a coefficient of \(-3a_{n-1}\) for \(x^n\) in \(-3xa(x)\text{.}\) Now add this to \(a(x)\text{.}\) This may be easier to see as written below:

We see that this gives

and we know that

so \((1-3x)a(x)=3-1/(1-x)\text{.}\) Dividing through by \(1-3x\) gives

Now it's time to apply what we learned in the preceding sections of this chapter. The denominator is already factored, so we can immediately apply the method of partial fractions to the second fraction. If

then \(A+B=-1\) and \(-3A-B=0\text{,}\) so \(B=-3A\text{,}\) which gives \(-2A=-1\text{,}\) so \(A=1/2\) and \(B=-3/2\text{.}\) Thus,

The coefficient of \(x^n\) in the first of these terms is \(1/2\text{,}\) while in the second term, the coefficient of \(x^n\) is \((3/2)3^n\text{.}\) Thus, \(a_n=1/2+(3/2)3^n\text{.}\) Since our generating function began with \(a_0x^0\text{,}\) this formula applies for every \(n \ge 0\text{.}\)

When going through so much algebra, it's easy to make a mistake somewhere along the way, so it's wise to do some double-checking. For a recursively-defined sequence, if the formula you work out gives the correct answer for the first three or four terms of the sequence, then it's very likely that you've done the calculations correctly. Let's check the first three terms of this one. We know from our initial condition that \(a_0=2\text{,}\) and our new formula gives

Using the recursive relation, we should have \(a_1=3(2)-1=5\text{,}\) and our formula gives

Finally, the recursive relation gives \(a_2=3(5)-1=14\text{,}\) while our formula gives

You can see the benefit to having an explicit formula if you were asked to work out \(a_{100}\text{.}\) Clearly, it's much easier to determine \(1/2+(3/2)3^{100}\) than to apply the recursive relation one hundred times.

The generating function for this sequence is

Again, we'll use the recursive relation, which we rearrange as

for every \(n \ge 3\text{.}\) We want to end up with a polynomial in which the coefficient of \(x^m\) looks like \(b_m-b_{m-1}+2b_{m-3}\text{,}\) so that we'll be able to use the recursive relation to replace this by \(0\text{.}\) In order to do this, we'll take \(b(x)\) (to get the \(b_mx^m\) piece), minus \(xb(x)\) (to get the \(-b_{m-1}x^m\) piece), plus \(2x^3b(x)\) (to get the \(+2b_{m-3}x^m\) piece).

The result looks like:

We see that this gives

Dividing through by \(1-x+2x^3\) gives

If we want to be able to do anything with this, we need to factor the denominator. Although we don't have a general method for factoring cubic polynomials, in this case it's not hard to see that \(-1\) is a zero of the polynomial (because \(1-(-1)+2(-1)^3=0\)), and hence \(x+1\) is a factor of the polynomial. You will not be expected to factor cubic polynomials yourself in this course, so we won't review polynomial long division, but if you recall polynomial long division (or look it up in some other source), you can use it to determine that

In any case, you can multiply the right-hand side out to verify that it is true.

Now it's time to use the factoring formula, with \(a=2\text{,}\) \(b=-2\text{,}\) and \(c=1\text{,}\) to factor \(2x^2-2x+1\text{.}\) This gives

Having factored

we now apply the method of partial fractions to split this up into three separate pieces.

If

then this gives us three equations:

(from the coefficient of \(x^2\));

(from the coefficient of \(x\)); and \(A+B+C=1\) (from the constant term). The second of these simplifies to \(-2A+iB-iC=-1\text{.}\)

The algebra can be done in different ways and gets a bit ugly, but these three equations can be solved, resulting in \(A=3/5\text{,}\) \(B=(2-i)/10\text{,}\) \(C=(2+i)/10\text{.}\)

Thus,

The coefficient of \(x^n\) in the first of these terms is \((3/5)(-1)^n\text{;}\) in the second, it is \(((2-i)/10))(1+i)^n\text{,}\) and in the third, it is \(((2+i)/10)(1-i)^n\text{.}\)

We conclude that for every \(n \ge 0\text{,}\) we have

It is somewhat surprising that these formulas involving complex numbers will always work out (when \(n\) is an integer) to be not only real numbers, but integers! Once again, we should check this formula for several values of \(n\) to ensure we haven't made errors in our calculations along the way.

From the initial conditions, \(b_0=1\text{.}\) Our formula gives

From the initial conditions, \(b_1=0\text{.}\) Our formula gives

Finally, the initial conditions gave \(b_2=1\text{,}\) and our formula gives

We could continue, but this is sufficient verification to inspire reasonable confidence.