254 16. Answers to Exercises
1.8.7. Both sides count the number of ways to divide ana-element set
into three sets witha−b,b−c, andcelements.
2 Combinatorial Tools
2.1 Induction
2.1.1. One ofnandn+ 1 is even, so the productn(n+ 1) is even. By
induction: true forn=1;ifn>1, thenn(n+1)=(n−1)n+2n, and
n(n−1) is even by the induction hypothesis, 2nis even, and the sum of
two even numbers is even.
2.1.2. True forn=1.Ifn>1, then
1+2+···+n=(1+2+···+(n−1)) +n=(n−1)n
2+n=n(n+1)
2.
2.1.3. The youngest person will countnhandshakes. The 7th oldest will
count 6 handshakes. So they count1+2+···+nhandshakes. We already
know that there aren(n+1)/2 handshakes.
2.1.4. Compute the area of the rectangle in two different ways.
2.1.5. By induction onn. True forn=2.Forn>2, we have
1 ·2+2·3+3·4+···+(n−1)·n=
(n−2)·(n−1)·n
3+(n−1)·n=
(n−1)·n·(n+1)
3.
2.1.6.Ifnis even, then 1 +n=2+(n−1) =···=
(n
2 −^1)
+n 2 =n+1, sothe sum isn 2 (n+1)=n(n 2 +1).Ifnis odd, then we have to add the middle
term separately.
2.1.7.Ifnis even, then 1+(2n−1) = 3+(2n−3) =···=(n−1)+(n+1) =
2 n, so the sum isn 2 (2n)=n^2. Again, ifnis odd, then the solution is similar,
but we have to add the middle term separately.
2.1.8. By induction. True forn=1.Ifn>1, then
12 +2^2 +···+(n−1)^2 =(
12 +2^2 +···+(n−1)^2)
+n^2=(n−1)n(2n−1)
6+n^2 =n(n+ 1)(2n+1)
6.
2.1.9. By induction. True forn=1.Ifn>1 then
20 +2^1 +2^2 +···+2n−^1 =(2^0 +2^1 +···+2n−^2 )+2n−^1
=(2n−^1 −1) + 2n−^1 =2n− 1.