2.9. EXERCISES 25
15. Consider the first five rows of Pascal’s1 triangle
11 1
1 2 11 3 3 1
1 4 6 4 1
What is the sixth row? Now consider that (x+ y)1 = 1x+1y , (x+ y)2 = x2 +2xy+y2, and (x+ y)3 = x3 +3x2y+3xy2 + y3. Give a conjecture about that (x+ y)5.
16. Based on Problem 15 conjecture a formula for (x+ y)n and prove your conjecture byinduction. Hint: Letting the numbers of the nth row of Pascal’s triangle be denoted by(n
0
),(n
1
), · · · ,
(nn
)in reading from left to right, there is a relation between the numbers
on the (n+1)st row and those on the nth row, the relation being(n+1
k
)=(n
k
)+( n
k−1
).
This is used in the inductive step.
17. Let(n
k
)≡ n!
(n−k)!k! where 0! ≡ 1 and (n+1)! ≡ (n+1)n! for all n ≥ 0. Prove that
whenever k ≥ 1 and k ≤ n, then(n+1
k
)=(n
k
)+( n
k−1
). Are these numbers,
(nk
)the
same as those obtained in Pascal’s triangle? Prove your assertion.
18. The binomial theorem states (a+b)n = ∑nk=0(n
k
)an−kbk. Prove the binomial theorem
by induction. Hint: You might try using the preceding problem.
19. Show that for p ∈ (0,1) ,∑nk=0(n
k
)kpk (1− p)n−k = np.
20. Show that for all n ∈ N,(1+ 1
n
)n ≤(1+ 1
n+1
)n+1. Hint: Show first that
(nk
)=
n·(n−1)···(n−k+1)k! . By the binomial theorem,
(1+
1n
)n
=n
∑k=0
(nk
)(1n
)k
=n
∑k=0
k factors︷ ︸︸ ︷n · (n−1) · · ·(n− k+1)
k!nk .
Now consider the term n·(n−1)···(n−k+1)k!nk and note that a similar term occurs in the
binomial expansion for(1+ 1
n+1
)n+1except that n is replaced with n+ 1 wherever
this occurs. Argue the term got bigger and then note that in the binomial expansionfor(1+ 1
n+1
)n+1, there are more terms.
21. Prove by induction that for all k ≥ 4, 2k ≤ k!
22. Use the Problems 21 and 20 to verify for all n ∈ N,(1+ 1
n
)n ≤ 3.
23. Prove by induction that 1+∑ni=1 i(i!) = (n+1)!.
24. I can jump off the top of the Empire State Building without suffering any ill effects.Here is the proof by induction. If I jump from a height of one inch, I am unharmed.Furthermore, if I am unharmed from jumping from a height of n inches, then jumping
1Blaise Pascal lived in the 1600’s and is responsible for the beginnings of the study of probability.