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 + 1n = 0, 1, \dots

or

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

Okay, it is the time to jump to another level.

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} + nn = 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.

The answer is

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!

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: