Quod Erat Demonstrandum

2009/08/30

Finding general term by generating function

It is extremely easy to set up questions on number pattern, like

1, 3, 8, 19, 42, 89, ?

for more details, we may tabulate the question as:

the question is, when $n = 6$, what is the value of $a_n$?

My first reply to such kind of question is

“no need to do"

because, even we know the first several terms in a number sequence, like

1, 3, 8, 19, 42, 89

then ANY number can be the next one!

[SBA]
Please give examples to illustrate the statement above.

However, if we restrict the question a bit, it may be more meaningful.

For instance, if the sequence above satisfying the following relation:

$a_n = ha_{n - 1} + kn$ ($n = 1,2, \dots$)

where $h, k$ are constants.

Then, to determine the values of $h, k$ will be a question for junior form students.

Okay, let me illustrate that SAME materials can be used in different levels.

（Level 1）For form 2 or 3 students, the question is about solving simultaneous equations.

Once we know the relation $a_n = ha_{n - 1} + kn$,

put $n = 1$, $3 = h + k$;
put $n = 2$, $8 = 3h + 2k$;

it is easy to have $h = 2, k = 1$, and thus $a_n = 2a_{n - 1} + n$.

（Level 2）For form 1 students, they may not know how to solve simultaneous equations and it should be set in the way that they could solve it by just observing the pattern and do some induction.

As for example, we add two more columns $a_{n + 1} - n$ and $2a_n$,

Form 1 students, could you identify the relation between $a_{n + 1} - n$ and $2a_n$?

Could you give an equation connecting $a_{n + 1} - n$ and $2a_n$?

May be, you could write down

$a_{n + 1} - n - 1 = 2a_n$

May be, it is a dream…

Anyway, we can conclude that

$a_{n + 1} = 2a_n + n + 1$$n = 0, 1, \dots$

or

$a_n = 2a_{n - 1} + n$$n = 1, 2, \dots$

We are not satisfying with the recurrence relation above, could we find out the explicit expression of the general term $a_n$?

Some years ago, I had introduced generating function（生成函數）in my forum which is a powerful tool of finding general terms.

The procedure is as follows.

Starting something ‘from God’, we consider a power series（冪級數）with $a_n$ as coefficients（係數）, i.e.

Let $G \equiv a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$

This $G$ is an example of generating function.

Finding $a_n$ is exactly the same as finding the coefficients of $G$.

If we can determine $G$ explicitly, the problem will be solved.

But, how?

Let’s make use of the recurrence relation $a_n = 2a_{n - 1} + n$$n = 1, 2, \dots$）.

Students, think about that, how do we make the coefficients in the power series to be involving something like $2a_{n - 1} + n$? Urm, intentionally, try to make the change by considering

$(2a_0 + 1) + (2a_1 + 2)x + (2a_2 + 3)x^2 + (2a_3 + 4)x^3 + \dots$ – – – – – – (*)

just a bit rearrangement, yield

$2(a_0 + a_1x + a_2x^2 + a_3x^3 + \dots) + (1 + 2x + 3x^2 + 4x^3 + \dots)$

（Here, students you may point out that the series should be absolutely convergent to guarantee that there is no change in the limit after a rearrangement. Yes, you are right. I remember when I set up similar questions in a school examination paper, my panel head required me to give clearly instruction, then I gave $|x| < 1$ as a condition. But, the use of generating function is something about the ‘format’, not something about analysis. Throughout the following discussion, we will assume that the series is convergent absolutely on certain domain.）

and the above will become

$2G + \frac{1}{(1 - x)^2}$

on the reason that

$1 + x + x^2 + x^3 + x^4 + \dots = \frac{1}{1 - x}$ （sum of G.S.）

Now, differentiate the above with respect to $x$, get

$1 + 2x + 3x^2 + 4x^3 + \dots = \frac{1}{(1 - x)^2}$

[SBA]
Is it always true in saying that $\frac{d}{dx}(f_1(x) + f_2(x) + \dots)$ = $\frac{df_1}{dx} + \frac{df_2}{dx} + \dots$

Thus, (*) can be expressed as

$2G + \frac{1}{(1 - x)^2}$ – – – – – – (**)

On the other hand, the reason why we made the coefficients of $G$ to be $2a_{n - 1} + n$ is for converting them into $a_n$, thus (*) is actually

$a_1 + a_2x + a_3x^2 + a_4x^3 + \dots$
$\equiv \frac{1}{x}(a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \dots)$
$\equiv \frac{1}{x}(a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \dots - a_0)$
$\equiv \frac{1}{x}(G - 1)$

Compare with (**), we have

$2G + \frac{1}{(1 - x)^2} \equiv \frac{1}{x}(G - 1)$

（Level 3）Now, it is something about form 3 and 4 students, determine the expression of $G$.

That is

$G \equiv \frac{x^2 - x + 1}{(1 - 2x)(1 - x)^2}$

Okay, form 3 or 4 students, this is only a question about "making $G$ as the subject", try to verify it on your own.

（Level 4）Now, we need senior form secondary mathematics. How to find coefficients of $G$? It involves two topics: partial fractions（部份分式）and sum of G.S.

For form 6 and 7 students, try to resolve $\frac{x^2 - x + 1}{(1 - 2x)(1 - x)^2}$ into partial fractions. I urge you to solve it on your own vividly as your revision.

$G \equiv \frac{3}{1 - 2x} - \frac{1}{1 - x} - \frac{1}{(1 - x)^2}$

Now, form 5 level: sum of G.S., i.e.

$\frac{1}{1 - x} \equiv 1 + x + x^2 + x^3 + \dots$
$\frac{2}{1 - 2x} \equiv 2(1 + 2x + (2x)^2 + (2x)^3 + \dots)$
$\frac{1}{(1 - x)^2} \equiv 1 + 2x + 3x^2 + 4x^3 + \dots$

thus

$G$
$\equiv (3(1 + 2x + (2x)^2 + (2x)^3 + \dots) - (1 + x + x^2 + x^3 + \dots) - (1 + 2x + 3x^2 + 4x^3 + \dots)$
$\equiv (3 - 2) + (3(2) - 3)x + (3(2^2) - 4)x^2 + (3(2^3) - 5)x^3 + \dots$

Behold, the pattern of coeffcients of each term can be identified clearly. The coefficient of $x^n$ is $3(2^n) - (n + 2)$, and also the coefficients of $x^n$ is $a_n$ as set; thus

$a_n = 3(2^n) - n - 2$ – – – – – – (***)

Go back to the original question, that is, evaluating $a_6$. Of course, we may make use of the recurrence relation $a_n = 2a_{n - 1} + n$, obtaining

$a_6 = 2a_5 + 6 = 2 \times 89 + 6 = 184$

Or, we may put $n = 6$ into (***), obtaining $a_6 = 3(2^6) - 6 - 2 = 184$

Yes, using the recurrence relation is easier, however, if I ask you to find $a_{2009}$, it may be better to use (***).

Finished? No, being a mathematics teacher, I wanna have some ideas of setting questions. Now, based on the materials above, I can set up at least 2 M.I. questions.

1. Let $a_0 = 1$, $a_n = 2a_{n - 1} + n$ ($n = 1, 2, \dots$). Prove by mathematical induction that $a_n = 3(2^n) - n - 2$ for any non negative integer $n$. (Trivial!)

To set up an 'advanced' M.I. question, we may observe the first serval terms in {$a_n$} by using the recurrence relation:

$a_0 = 1$
$a_1 = 2(1) + 1 = 3$
$a_2 = 2(3) + 2 = 2^3$
$a_3 = 2(2^3) + 3 = 2^4 + 3$
$a_4 = 2^5 + 2*3 + 4$
$a_5 = 2^6 + 2^2*3 + 2*4 + 5$
$a_6 = 2^7 + 2^3*3 + 2^2*4 + 2*5 + 6$
$\dots$

Hence we can create another question:

2. Let $a_3 = 19$ and $a_n = 2^{n+1} + 3(2^{n-3}) + 4(2^{n-4}) + 5(2^{n-5}) + \dots + 2(n-1) + n$ (for $n = 3,4, \dots$). Prove by mathematical induction that $a_n = 3(2^n) - n - 2$ for all integer $n \ge 3$.

Finally, students, you may find the method of using generating function is a bit clumsy, especially for this particular question. You may have smarter methods to solve for $a_n$. However, all I want is to introduce the method of using generating function and it is known that some questions can ONLY be solved by using generating function. Hope to share more next, bye bye!