1.8. EXERCISES 31
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 (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. Using the binomial theorem prove that for all n∈N,(1+ 1
n
)n ≤(1+ 1
n+1
)n+1. Hint:
Show first that(n
k
)= 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 whereever
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 jumpingfrom a height of n+1 inches will also not harm me. This is self evident and providesthe induction step. Therefore, I can jump from a height of n inches for any n. Whatis the matter with this reasoning?
25. All horses are the same color. Here is the proof by induction. A single horse is thesame color as himself. Now suppose the theorem that all horses are the same coloris true for n horses and consider n+1 horses. Remove one of the horses and use theinduction hypothesis to conclude the remaining n horses are all the same color. Putthe horse which was removed back in and take out another horse. The remaining nhorses are the same color by the induction hypothesis. Therefore, all n+1 horses arethe same color as the n−1 horses which didn’t get moved. This proves the theorem.Is there something wrong with this argument?