Mathematics for Computer Science

15.6. References 659

and hence

CD

1 ̇

p

1 4x

2x

: (15.27)

LetD.x/WWD2xC.x/. ExpressingDas a power series

D.x/Dd 0 Cd 1 xCd 2 x^2 C


;

we have

cnD

dnC 1

2

: (15.28)

(d)Use (15.27), (15.28), and the value ofc 0 to conclude that

D.x/D 1 

p

1 4x:

(e)Prove that

dnD

.2n3/
.2n5/


 5 
 3 
 1 
 2 n

nŠ

:

Hint:dnDD.n/.0/=nŠ

(f)Conclude that

cnD

1

nC 1

2n

n

!

:

Exam Problems

Problem 15.20.
Define the sequencer 0 ;r 1 ;r 2 ;:::recursively by the rule thatr 0 WWD 1 and

rnWWD7rn 1 C.nC1/ forn > 0:

LetR.x/WWD

P 1

0 rnx

nbe the generating function of this sequence. ExpressR.x/

as a quotient of polynomials or products of polynomials. You donothave to find a
closed form forrn.

Problem 15.21.
Alyssa Hacker sends out a video that spreads like wildfire over the UToob network.
On the day of the release—call itday zero—and the day following—call itday
one—the video doesn’t receive any hits. However, starting with day two, the num-
ber of hits,rn, can be expressed as seven times the number of hits on the previous
day, four times the number of hits the day before that, and the number of days that
has passed since the release of the video plus one. So, for example on day 2, there
will be 7  0 C 4  0 C 3 D 3 hits.