Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

34 Combinatorics of Compositions and Words

with initial condition a

is given by a

= a



j=1

q(j). In particular, if

q(j)=b for all j, then the solution is of the form a

Iteration can also work nicely for nonlinear recurrence relations of order

one.

Example 2.20 Consider the recurrence relation

=2a

n−1

,n≥ 1,a

=3,

which is nonlinear because of the squared term. Repeated substitution gives

=2· a

n−1

=2(2a

n−2

)

=2·2

·(2a

n−3

)

= ···

=2· 2

·2

···2

n−1

−1

·3

The explicit formula for a

can be computed using the Maple code

rsolve({a(n)=2*a(n-1)^2,a(0)=3},a(n));

or the Mathematica code

RSolve[{a[n]==2 a[n - 1]^2, a[0]==3}, a[n], n]

2.2.3 Characteristic polynomial

We now describe how to derive an explicit solution for a linear recurrence

relation with constant coeﬃcients of order r of the form

+ α

n−1

+ α

n−2

+ ···+ α

n−r

= q(n) for all n ≥ 0, (2.2)

where q(n) is a polynomial in n, not depending on a

Solving a nonhomogeneous recurrence relation, when possible, requires solv-

ing the corresponding homogeneous recurrence relation as part of the process,

so we will start by solving linear homogeneous recurrence relations with con-

stant coeﬃcients of the form

+ α

n−1

+ α

n−2

+ ···+ α

n−r

=0 foralln ≥ 0. (2.3)

Like many results in mathematics, Theorem 2.22 below arose from an ed-

ucated guess and then working out the algebraic details. Taking inspiration

from Example 2.19, where the solution is of the form a

·b

, one might guess

that for linear recurrence relations with constant coeﬃcients, the solution may

be of the form ξ

, give or take a multiplicative constant. Checking the guess

by substituting it into the recurrence relation and taking out common factors

reduces to ﬁnding the roots of the polynomial

Δ(x)=x

+ α

r−1

+ α

r−2

+ ···+ α

in order to determine the value of ξ.

Basic Tools of the Trade 35

Deﬁnition 2.21 The polynomial Δ(x)=x

+ α

r−1

+ α

r−2

+ ···+ α

called the characteristic polynomial of the recurrence relation

+ α

n−1

+ α

n−2

+ ···+ α

n−r

=0.

By the Fundamental Theorem of Algebra, the characteristic polynomial has

r (possibly complex) roots, counting multiplicities. The following theorem

tells us how the solutions look in the case of roots with multiplicity bigger

than one, and ensures that indeed there are r independent solutions for a

linear recurrence relation with constant coeﬃcients of order r.

Theorem 2.22 Let ξ ∈ C be any root of

Δ(x)=x

+ α

r−1

+ α

r−2

+ ···+ α

with multiplicity m, then the basic solutions n

, i =0, 1,...,m− 1, satisfy

(2.3).

Proof See Exercise 2.10. 2

We now form a linear combination of the r diﬀerent basic solutions given

in Theorem 2.22. It is easy to show that the resulting sequence is a solution

to (2.3) because of the linearity of the recurrence relation.

Theorem 2.23 If a

(n),...,a

(n) are diﬀerent sequences satisfying (2.3),

then for any constants c

,...,c

∈ C, the sequence a



j=1

· a

(n),

called the general solution,satisﬁes(2.3).

Now, for a given linear homogeneous recurrence relation as described in

(2.3) with r initial conditions, we can obtain an explicit formula using the

following steps:

1. Find all the roots of the characteristic polynomial Δ(x) and their mul-

tiplicity.

2. Determine the general solution as described in Theorem 2.23.

3. Use the initial conditions to obtain a linear system of r equations in r

unknowns, then solve it to obtain a speciﬁc solution.

Example 2.24 Consider the recurrence relation a

=4a

n−1

−5a

n−2

+2a

n−3

with initial conditions a

=1, a

=1,anda

=2. The characteristic polyno-

mial of this recurrence relation is

Δ(x)=x

− 4x

+5x −2=(x − 2)(x

− 2x +1)=(x − 2)(x − 1)

36 Combinatorics of Compositions and Words

The characteristic polynomial has two roots: ξ =2with multiplicity one, and

ξ =1with multiplicity two. From Theorem 2.23, we obtain that the general

solution for this recurrence relation is given by

= c

· 2

+ c

· 1

+ c

·n · 1

= c

· 2

+ c

·n.

Using the initial conditions results in the equations c

=1, 2 c

1,and4 c

+ c

+2c

=2. The values of c

can be computed by using

the Maple code

solve({c_1*2^0+c_2+c_3*0=1,c_1*2^1+c_2+c_3*1=1,

c_1*2^2+c_2+c_3*2=2},{c_1,c_2,c_3});

or the Mathematica code

Solve[{c[1] 2^0+c[2]+c[3] 0==1, c[1] 2^1+c[2]+c[3] 1==1,

c[1] 2^2+c[2]+c[3] 2==2},{c[1],c[2],c[3]}]

We obtain that c

=1, c

=0,andc

= −1, which implies that the explicit

formula is given by a

− n.

Note that a homogeneous linear recurrence relation with constant coeﬃ-

cients of order two can always be solved (as we can compute the exact roots

using the quadratic formula). For higher orders, the Fundamental Theorem of

Algebra guarantees that there are as many roots as the order of the recurrence

relation, but we do not have formulas to ﬁnd the exact roots unless we can

factor the characteristic polynomial nicely.

Example 2.25 (Fibonacci and Lucas Sequences) We can now ﬁnd explicit

solutions for the Fibonacci and the Lucas sequence. Recall that the two se-

quences have the same recurrence relation a

= a

n−1

+ a

n−2

,withinitial

conditions F

=0, F

=1for the Fibonacci sequence and L

=2, L

=1for

the Lucas sequence. Since the recurrence relation is the same, they both have

the same characteristic polynomial Δ(x)=x

− x − 1, and hence the same

general solution. Using the quadratic formula, we obtain that ξ

1,2

1±

√

and thus, the general solution is given by

= c



√



+ c



1 −

√



Note that it is customary in the context of the Fibonacci sequence to deﬁne

α =

√

,theGolden Ratio

Φ,andβ =

1−

√

. The initial conditions for the

Fibonacci sequence give 0=c

+ c

and 1=c

·α + c

·β. Using any method

http://mathworld.wolfram.com/GoldenRatio.html

Basic Tools of the Trade 37

to solve a system of two equations, we obtain c

=1/

√

5 and c

= −1/

√

and thus

√



√



−



1 −

√





. (2.4)

This formula for the Fibonacci sequence is somewhat surprising, as the pow-

ers of irrational numbers balance in just the correct way to give an integer

result for any value of n (seeExercise2.9). This formula was ﬁrst derived

by Abraham De Moivre

, and independently by Daniel Bernoulli

.Forthe

derivation of the explicit formula for the Lucas sequence see Exercise 2.8. We

can ﬁnd the explicit formula for F

by using the following Maple code:

rsolve({a(n)=a(n-1)+a(n-2),a(0)=0,a(1)=1},a(n));

Using the corresponding Mathematica code

RSolve[{a[n]==a[n - 1] + a[n - 2], a[0]==0, a[1]==1},a[n],n]

does not result in an explicit formula, but rather in the answer that a

is the

n-th Fibonacci number, a function that is deﬁned in Mathematica:

{{a[n] -> Fibonacci[n]}}.

Now we are ready to indicate how to solve a linear nonhomogeneous recur-

rence relation with constant coeﬃcients. Theorem 2.26 gives the form of the

general solution, which consists of two parts.

Theorem 2.26 The general solution of the nonhomogeneous linear recur-

rence relation with constant coeﬃcients of order r as given in (2.2) is of the

form h(n)+p(n),whereh(n) is the general solution of the associated homo-

geneous recurrence relation (2.3),andp(n) is any solution of (2.2).

The solution p(n) in Theorem 2.26 is called the particular solution. To ﬁnd

the general solution for a nonhomogeneous recurrence relation, we need to use

the following steps:

1. Find the general solution for the associated homogeneous recurrence

relation.

2. Guess a particular solution.

3. Use the initial conditions to determine the speciﬁc solution.

The diﬃcult part is to ﬁnd the particular solution, which often involves

guess and check. There is no approach that works for all types of functions

that may occur on the right-hand side of (2.2). However, for certain common

functions, the form of the particular function is known. If p(n)isaconstant

http://www-groups.dcs.st-and.ac.uk/∼history/Mathematician/De Moivre.html

http://www-groups.dcs.st-and.ac.uk/∼history/Mathematicians/Bernoulli Daniel.html

38 Combinatorics of Compositions and Words

multiple of a function listed on the left-hand side of Table 2.4, then the func-

tion given on the right-hand side is a particular solution (if it is not also a so-

lution of the homogeneous recurrence relation). The constants d, r,andθ are

given, while the constants c

have to be determined from the given recurrence

relation. If q(n) is a linear combination of functions given on the left-hand

side of Table 2.4, and none of these functions is a solution of the homogeneous

recurrence relation, then the particular solution is a linear combination of the

respective functions given on the right-hand side of Table 2.4. For example,

if q(n)=d

+cos(θn), then p(n)=c

· d

+ c

sin(θn)+c

cos(θn). For a

more detailed discussion of how to solve nonhomogeneous linear recurrence

relations with constant coeﬃcients, speciﬁcally what to do when the candi-

date particular solution also solves the homogeneous recurrence relation, see

[78, 182, 189].

TABLE 2.4: Particular solutions for certain q(n)

q(n) p(n)

d c

c · d

,r ∈ N c

+ ···+ c

n + c

,r ∈ N d

+ ···+ c

n + c

)

sin(θn)orcos(θn) c

sin(θn)+c

cos(θn)

sin(θn)ord

cos(θn) c

sin(θn)+c

cos(θn)

To demonstrate how to solve a nonhomogeneous recurrence relation, we

revisit Example 2.10.

Example 2.27 (Words avoiding substrings) The recurrence relation for the

number of words on {1, 2, 3} that do not start with 3 and do not contain the

substrings 22, 31,and32 is given by

= a

n−1

+ a

n−2

+1, (2.5)

with initial conditions a

=1and a

=2. The associated homogeneous recur-

rence relation is the same as the one for the Fibonacci sequence, and there-

fore, the general solution is given by a

= c

(see Example 2.25)with

α =(1+

√

5)/2 and β =(1−

√

5)/2. The next step is to ﬁnd a particular

solution. In this case, the polynomial q(n) is a constant, so the particular

solution is constant too, say p(n)=c. Substituting this particular solution

into (2.5) leads to c = c + c +1 or c = −1. Thus, the general solution for the

nonhomogeneous recurrence relation is given by

= c

+ c

− 1 (2.6)

Basic Tools of the Trade 39

and substituting the initial conditions results in the system of equations

1=c

+ c

− 1 and 2=c

α + c

β − 1.

Using standard methods to solve a system of two equations gives c

√

5+2

√

and c

√

5−2

√

. The sequence of values for a

for n =0,...,10 is given by

1, 2, 4, 7, 12, 20, 33, 54, 88, 143 and 232. These ﬁrst few values satisfy

= F

n+3

−1. Comparing this expression with (2.6), the pattern would work

in general if c

√

and c

= −

√

, which can be shown to be true

using some algebra. Substituting these coeﬃcients into the speciﬁc solution

then gives a

√



− β



− 1=F

n+3

− 1. Oncemorewecanﬁndthe

explicit formula for a(n) by using the Maple code

rsolve({a(n)=a(n-1)+a(n-2)+1,a(0)=1,a(1)=2},a(n));

In Mathematica,weuse

RSolve[{a[n]==a[n-1]+a[n-2]+1,a[0]==1,a[1]==2},a[n],n]

which returns an answer in terms of the Fibonacci and Lucas sequences:

LucasL is a built-in Mathematica function which computes the n-th Lucas

number. The two expressions for a

, when set equal to each other, yield that

+ L

= F

n+3

2.3 Generating functions

We will now discuss another important tool to obtain explicit formulas from

recurrence relations, namely generating functions. Generating functions are

formal power series, and we will discuss the theory of formal power series

after stating the deﬁnitions and some basic examples. There are two main

types of generating functions used in combinatorics, ordinary and exponential

generating functions.

Deﬁnition 2.28 The ordinary generating function for the sequence {a

}

n∈N

is given by A(x)=



n≥0

,andtheexponential generating function for

the sequence {a

}

n∈N

is given by E(x)=



n≥0

The name generating function comes from the fact that the power series

expansion of the functions A(x)andE(x) “generates” the values of the se-

quence as the coeﬃcients of the terms x

and

, respectively. With tools

40 Combinatorics of Compositions and Words

such as Maple and Mathematica, knowing the generating function for a se-

quence allows for easy computation of any value, even if we cannot ﬁnd an

explicit formula for the coeﬃcients. Since we will primarily deal with ordi-

nary generating functions, we will omit “ordinary” in the remainder of the

book. We start by computing the generating functions for some well known

sequences.

Example 2.29 (Fibonacci Sequence) We will derive the generating function

for the Fibonacci sequence and from it the explicit formula given in Example

2.25. We start with the recurrence relation for the Fibonacci numbers, F

n−1

+ F

n−2

for n ≥ 2, with initial conditions F

=0,F

=1.Inorderto

connect this recurrence relation to the generating function, we multiply the

recurrence relation by x

, and then sum over the values of n for which the

recurrence is valid:



n≥2



n≥2

n−1



n≥2

n−2

Let F (x)=



n≥0

be the generating function of the Fibonacci sequence.

We express each of the series in terms of F (x)(this is where the initial terms

come in), factor out appropriate powers of x so that the remaining powers

match the sequence index, and re-index the series on the right-hand side of

the equation to obtain

F (x) −F

− F

x = x



n≥2

n−1

+ x



n≥2

n−2

= x (F (x) − F

)+x

F (x). (2.7)

Solving for F(x) gives

F (x)=

1 − x − x

−(x + α)(x + β)

, (2.8)

where α =

√

and β =

1−

√

. To obtain the coeﬃcients of x

, we need

the Taylor series expansion of F (x). Instead of using the deﬁnition of the

Taylor series expansion which involves derivatives of the function, we make

use of functions whose Taylor series we know. One of these is the geometric

series



n≥0

1−t

, which will be used repeatedly in computing generating

functions. Since αβ = −1, we can rewrite the denominator as product of

factors in the correct form for the geometric series:

−(x + α)(x + β)

(−βx− βα)

−1

(−αx− αβ)

(1 − βx)(1 − αx)

We then compute the partial fraction decomposition of the function, that is,

we determine the constants c

and c

satisfying

(1 − βx)(1 − αx)

1 − αx

1 − βx

Basic Tools of the Trade 41

Solving for the constants in the numerator gives c

α−β

√

and c

−β

α−β

−β

√

.Thus,

F (x)=

1 − x − x

√



1 − αx

−

1 − βx



Using the geometric series, this gives

F (x)=

√

⎛

⎝



n≥0

(αx)

− β



n≥0

(βx)

⎞

⎠



n≥1

√

(α

− β

) x

Now we can read oﬀ F

as the coeﬃcient of x

to obtain F

√

(α

− β

)

as in Example 2.25. In Maple, the generating function can be obtained from

the recurrence relation by giving an optional argument to rsolve:

rsolve({F(n)=F(n-1)+F(n-2),F(0)=0,F(1)=1},F,’genfunc’(x));

The Mathematica function RSolve does not have this option, but we can use

RSolve in conjunction with GeneratingFunction (Mathematica Version 7.0)

to obtain the generating function.

sol = RSolve[{F[n]==F[n-1]+F[n-2], F[0]==0, F[1]==1}, F[n], n];

GeneratingFunction[sol[[1, 1, 2]], n, x]

In Mathematica Version 6.0, we can use the following code to arrive at the

same answer:

sol = RSolve[{F[n]==F[n-1]+F[n-2], F[0]==0, F[1]==1}, F[n], n];

Sum[sol[[1, 1, 2]] x^n, {n,0,Infinity}] // FullSimplify

We will now give some examples of exponential generating functions. In

most cases, the exponential generating function will result in logarithmic or

exponential functions, unless the sequence terms contain factorials.

Example 2.30 To compute the exponential generating function for S

,the

number of permutations of [n](of which there are n!),weusethedeﬁnition

and obtain

E(x)=



n≥0



n≥0

1 − x

Example 2.31 Modifying Example 2.30 slightly, we derive the exponential

generating function for the sequence a

=(n − 1)!.Then

E(x)=



n≥1



n≥1

(n − 1)!



n≥1

= −log(1 − x),

where we make use of the known Taylor series expansion for the natural log-

arithm log(x). We can ﬁnd the generating function E(x) by using the Maple

function sum or the Mathematica function Sum, respectively:

42 Combinatorics of Compositions and Words

sum((n-1)!/n!*x^n,n=1..infinity);

Sum[(n - 1)!/n! x^n, {n, 1, Infinity}]

The last two examples show that it is convenient to use the exponential

generating function rather than the ordinary generating function when the

sequence terms or the recurrence relation involve factorial terms. Note also

that we have used the generating function in two diﬀerent ways: in Example

2.29 we started from the recurrence relation, multiplying the relation by x

and summing over n, then solving for the generating function. If we already

have an explicit formula, then we just use the deﬁnition.

In Example 2.29, we derived an explicit formula for the Fibonacci sequence

from the recurrence relation using the generating function approach. Pre-

viously (see Example 2.25) we derived the same formula from the solution

procedure for linear recurrence relations with constant coeﬃcients. Do we al-

ways have these two choices? The answer is yes, that is, any linear recurrence

relation with constant coeﬃcients canalsobesolvedusingthegenerating

function approach, as we will demonstrate now. Note that the generating

function approach has the advantage that we can solve the nonhomogeneous

recurrence relation directly, without ﬁrst solving the associated homogeneous

relation.

Lemma 2.32 Given a linear recurrence relation with constant coeﬃcients of

the form

+ α

n−1

+ α

n−2

+ ···+ α

n−r

= f(n) for all n ≥ r,

where α

,...,α

are constants and f(n) is any function, the associated gen-

erating function is given by

A(x)=



j=0



r−j−1

i=0



n≥r

f(n)x



j=0

. (2.9)

Proof Given a linear recurrence relation with constant coeﬃcients, we pro-

ceed as in Example 2.25, multiplying the recurrence relation by x

and sum-

ming over n ≥ r to obtain



n≥r

⎛

⎝



j=0

n−j

⎞

⎠



n≥r

f(n)x

Separating terms that are independent of n, and splitting oﬀ x

gives



j=0



n≥r

n−j



n≥r

f(n)x

Basic Tools of the Trade 43

or equivalently, after re-indexing the inner sum and writing it in terms of the

generating function,



j=0



A(x) −

r−j−1



i=0





n≥r

f(n)x

Solving for A(x) gives (2.9). 2

We can apply this formula to the nonhomogeneous recurrence relation of

Example 2.27.

Example 2.33 Let a

= a

n−1

+ a

n−2

+1 with initial conditions a

=1and

=2. The relevant parameters are r =2, α

=1, α

= α

= −1, f (n)=1

for all n, and therefore,



n≥2

f(n)x

= x



n≥0

1−x

. Substituting this

expression and the parameter values into (2.9), we obtain that

A(x)=

+ a

x)+α

1−x

+ α

x + α

1+x +

1−x

1 − x − x

(1 − x)(1 −x −x

)

1 − 2x + x

Maple is able to ﬁnd the generating function also in this case:

rsolve({a(n)=a(n-1)+a(n-2)+1,a(0)=1,a(1)=2},a,’genfunc’(x));

In Mathematica 7.0, we use once more RSolve and GeneratingFunction.

Note that RSolve expresses the answer as a linear combination of the Fi-

bonacci and Lucas sequences.

sol = RSolve[{a[n]==a[n-1]+a[n-2]+1, a[0]==1, a[1]==2}, a[n], n]

GeneratingFunction[sol[[1, 1, 2]], n, x] // Simplify

We will return to this example once we have developed a few more tools to

see how we can read oﬀ the explicit formula for {a

}

n≥0

from this generating

function.

In order for generating functions to be useful, we need to be able to add

and multiply them. However, we will not be concerned with questions of

convergence at this point, but rather work with formal power series. (We will

change our point of view in Chapter 8 to obtain results on the asymptotic

behavior of the coeﬃcients.) Let {a

→

}

→

n ∈N

be a sequence with k indices, L

be a ring (see Deﬁnition B.27), and L[x

,...,x

]=L[

→

x ]bethesetofall

polynomials in k indeterminates

→

x =(x

,...,x

) with coeﬃcients in L.