Page 389 - Understanding Machine Learning

Technical Lemmas 371

Using Stirling’s approximation we further have that

d
em d (m − d)
d
≤ 1 + √
d e (d + 1) 2πd(d/e) d

em m − d
d
= 1 + √
d 2πd(d + 1)
√
em
d d + 1 + (m − d)/ 2πd
= ·
d d + 1
em
d d + 1 + (m − d)/2
≤ ·
d d + 1
em
d d/2 + 1 + m/2
= ·
d d + 1
em m
d
≤ · ,
d d + 1
where in the last inequality we used the assumption that d ≤ m − 2. On the other
hand,
d+1 d
em em d em d
= · ·
d + 1 d d + 1 d + 1
em em 1
d
= · ·
d d + 1 (1 + 1/d) d
em em 1
d
≥ · ·
d d + 1 e
em m
d
= · ,
d d + 1
which proves our inductive argument.
Lemma A.6. For all a ∈ R we have
a
e + e −a a /2
2
≤ e .
2
Proof. Observe that
∞ n
a
a
e = .
n!
n=0
Therefore,
∞
a
e + e −a a 2n
= ,
2 (2n)!
n=0
and
∞ a 2n

2
e a /2 = .
n
2 n!
n=0
n
Observing that (2n)! ≥ 2 n! for every n ≥ 0 we conclude our proof.