Mathematics for Computer Science

Chapter 15 Generating Functions642

Reasoning as we did for the Fibonacci recurrence, we have

T.x/ D t 0 C t 1 x C 


 C tnxnC




2xT.x/ D  2t 0 x  


  2tn 1 xnC




1=.1x/ D  1  1x  


  1xnC




T.x/.12x/1=.1x/ D t 0  1 C 0x C 


 C 0xnC




D 1;

so

T.x/.12x/D

1

1 x

1 D

x

1 x

;

and
T.x/D

x

.12x/.1x/

:

Using partial fractions,

x

.12x/.1x/

D

c 1

1 2x

C

c 2

1 x

for some constantsc 1 ;c 2. Now multiplying both sides by the left hand denominator
gives
xDc 1 .1x/Cc 2 .12x/:

Substituting1=2forxyieldsc 1 D 1 and substituting 1 forxyieldsc 2 D 1 ,
which gives

T.x/D

1

1 2x

1

1 x

:

Finally we can read off the simple formula for the numbers of steps needed to move
a stack ofndisks:

tnDŒxnçT.x/DŒxnç



1

1 2x



Œxnç



1

1 x



D 2 n1:

15.4.3 Solving General Linear Recurrences

An equation of the form

f.n/Dc 1 f.n1/Cc 2 f.n2/C


Ccdf.nd/Ch.n/ (15.15)

for constantsci 2 Cis called adegreedlinear recurrencewith inhomogeneous
termh.n/.
The methods above can be used to solve linear recurrences with a large class of
inhomogeneous terms. In particular, when the inhomogeneous term itself has a gen-
erating function that can be expressed as a quotient of polynomials, the approach