108 CHAPTER 2 Discrete Mathematics

(b) Using part (a) show that

∑k

l=0

Ñ

k

l

é

(−1)llk = (−1)kk!

(Hint: this can be shown using induction^27 .)

(c) Conclude that ifC(x) = (x−1)k, a the solution ofC(u) =d,

whered=d, d, ...is written as

un=ank+ lower-degree terms inn,

thena=

d

k!

.

19. Let F 1 = 1, F 2 = 1, F 3 = 2,...be the Fibonacci sequence. Show
    that one has the curious identity

x

1 −x−x^2

=

∑∞

k=1

Fkxk.

(^27) Here’s how:
∑k
l=0
Ç
k
l
å
(−1)llk =
∑k
l=0
ñÇ
k− 1
l
å

• 
  

  Ç
  k− 1
  l− 1
  åô
  (−1)llk

  
  

  ∑k
  l=0
  Ç
  k− 1
  l
  å
  (−1)llk+
  ∑k
  l=0
  Ç
  k− 1
  l− 1
  å
  (−1)llk

  
  

  k∑− 1
  l=0
  Ç
  k− 1
  l
  å
  (−1)llk−
  k∑− 1
  l=0
  Ç
  k− 1
  l
  å
  (−1)l(l+ 1)k
  = −
  k∑− 1
  l=0
  Ç
  k− 1
  l
  å
  (−1)l
  k∑− 1
  m=0
  Ç
  k
  m
  å
  lm
  = −
  k∑− 1
  m=0
  k∑− 1
  l=0
  Ç
  k
  m
  åÇ
  k− 1
  l
  å
  (−1)llm
  = −
  k∑− 1
  m=0
  Çk
  m
  åk∑− 1
  l=0
  Çk− 1
  l
  å
  (−1)llm
  = −
  Ç
  k
  k− 1
  åk∑− 1
  l=0
  Ç
  k− 1
  l
  å
  (−1)llk−^1 (we’ve used (a))
  = −k·(−1)k−^1 (k−1)! = (−1)kk! (induction)