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
.2n 3/.2n 5/ 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.