Discrete Mathematics: Elementary and Beyond

62 3. Binomial Coefficients and Pascal’s Triangle

oftadds up to less thancA, the next block to less thanc^2 A, etc. Adding
up, we get that
B<cA+c^2 A+c^3 A...

On the right-hand side we only have to sum(m−t)/tterms, but we are
generous and let the summation run to infinity! The geometric series on
the right-hand side adds up to 1 −ccA, so we get that

B<

c

1 −c

A.

We need another inequality involvingAandB, but this is easy:

B+A<

1

2

22 m

(since the sum on the left-hand side includes only the left-hand side of
Pascal’s Triangle, and the middle element is not even counted). From these
two inequalities we get

B<

c

1 −c

A<

c

1 −c

(

1

2

22 m−B

)

,

and hence (

1+

c

1 −c

)

B<

c

1 −c

1

2

22 m.

Multiplying by 1−cgives thatB<c^1222 m, which proves the lemma.

3.8.1 (a) Check that the approximation in (3.8) is always between the lower

and upper bounds given in (3.9).

(b) Let 2m= 100 andt= 10. By what percentage is the upper bound in (3.9)

larger than the lower bound?

3.8.2Prove the upper bound in (3.9).

3.8.3Complete the proof of Lemma 3.8.1.

Review Exercises

3.8.4Find all values ofnandkfor which

n

k+1



=3

n

k



.

3.8.5Find the value ofkfor whichk

 99

k



is largest.