integer f (n) is not prime.
Proof. (Outline) Note that, because the coefficients are all positive and the
degree is greater than 1, we have f (1) > 1. Let b = f (1) > 1. Now, the polynomial
f (x) − b has a root 1, so f (x) − b = (x − 1)g(x) for some polynomial g. Then
f (x) = (x − 1)g(x) + b. Now note that f (b + 1) = bg(b) + b = b(g(b) + 1). If we can
now show that g(b) + 1 is an integer, then we have a nontrivial factoring
f (b + 1) = b(g(b) + 1), and f (b + 1) is not prime. To complete the proof, use the
fact that f (x) − b = (x − 1)g(x) has integer coefficients, and deduce that g(x) must
also have integer coefficients.
■
Chapter 10 Exercises
n2 + n
1. For every integer n ∈ N, it follows that 1 + 2 + 3 + 4 + ··· + n =
.
2
Proof. We will prove this with mathematical induction.
12 + 1
(1) Observe that if n = 1, this statement is 1 =
, which is obviously true.
2
277
(2) Consider any integer k ≥ 1. We must show that Sk implies Sk+1. In other
words, we must show that if 1 + 2 + 3 + 4 + · · · + k = k2+k
2
is true, then
(k + 1)2 + (k + 1)
1 + 2 + 3 + 4 + ··· + k + (k + 1) =
2
is also true. We use direct proof.
Suppose k ≥ 1 and 1 + 2 + 3 + 4 + · · · + k = k2+k
2
. Observe that
1 + 2 + 3 + 4 + ··· + k + (k + 1) =
(1 + 2 + 3 + 4 + ··· + k) + (k + 1) =
k2 + k
k2 + k + 2(k + 1)
+ (k + 1)
=
2
2
k2 + 2k + 1 + k + 1
=
2
(k + 1)2 + (k + 1)
=
.
2
Therefore we have shown that 1 + 2 + 3 + 4 + · · · + k + (k + 1) = (k+1)2+(k+1)
2
.
■
3. For every integer n ∈ N, it follows that 13 + 23 + 33 + 43 + ··· + n3 = n2(n+1)2
4
.
Proof. We will prove this with mathematical induction.
(1) When n = 1 the statement is 13 = 12(1+1)2
4
= 44 = 1, which is true.
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
13 + 23 + 33 + 43 + ··· + k3 = k2(k+1)2
4
. Observe that this implies the statement is
true for n = k + 1.
13 + 23 + 33 + 43 + ··· + k3 + (k + 1)3
=
(13 + 23 + 33 + 43 + ··· + k3) + (k + 1)3
=
k2(k + 1)2
k2(k + 1)2
4(k + 1)3
+ (k + 1)3
=
+
4
4
4
k2(k + 1)2 + 4(k + 1)3
=
4
(k + 1)2(k2 + 4(k + 1)1)
=
4
(k + 1)2(k2 + 4k + 4)
=
4
(k + 1)2(k + 2)2
=
4
(k + 1)2((k + 1) + 1)2
=
4
Therefore 13 + 23 + 33 + 43 + · · · + k3 + (k + 1)3 = (k+1)2((k+1)+1)2
4
, which means the
statement is true for n = k + 1.
■
278
Solutions
5. If n ∈ N, then 21 + 22 + 23 + ··· + 2n = 2n+1 − 2.
Proof. The proof is by mathematical induction.
(1) When n = 1, this statement is 21 = 21+1 − 2, or 2 = 4 − 2, which is true.
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
21 + 22 + 23 + ··· + 2k = 2k+1 − 2. Observe this implies that the statement is true
for n = k + 1, as follows:
21 + 22 + 23 + ··· + 2k + 2k+1
=
(21 + 22 + 23 + ··· + 2k) + 2k+1
=
2k+1 − 2 + 2k+1
=
2 · 2k+1 − 2
=
2k+2 − 2
=
2(k+1)+1 − 2
Thus we have 21 + 22 + 23 + · · · + 2k + 2k+1 = 2(k+1)+1 − 2, so the statement is true
for n = k + 1.
Thus the result follows by mathematical induction.
■
n(n + 1)(2n + 7)
7. If n ∈ N, then 1 · 3 + 2 · 4 + 3 · 5 + 4 · 6 + ··· + n(n + 2) =
.
6
Proof. The proof is by mathematical induction.
(1) When n = 1, we have 1 · 3 = 1(1+1)(2+7)
6
, which is the true statement 3 = 18
6 .
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
1 · 3 + 2 · 4 + 3 · 5 + 4 · 6 + ··· + k(k + 2) = k(k+1)(2k+7)
6
. Now observe that
1 · 3 + 2 · 4 + 3 · 5 + 4 · 6 + ··· + k(k + 2) + (k + 1)((k + 1) + 2) =
(1 · 3 + 2 · 4 + 3 · 5 + 4 · 6 + ··· + k(k + 2)) + (k + 1)((k + 1) + 2) =
k(k + 1)(2k + 7) +(k+1)((k+1)+2) =
6
k(k + 1)(2k + 7)
6(k + 1)(k + 3)
+
=
6
6
k(k + 1)(2k + 7) + 6(k + 1)(k + 3)
=
6
(k + 1)(k(2k + 7) + 6(k + 3))
=
6
(k + 1)(2k2 + 13k + 18)
=
6
(k + 1)(k + 2)(2k + 9)
=
6
(k + 1)((k + 1) + 1)(2(k + 1) + 7)
6
Thus we have 1·3+2·4+3·5+4·6+· · ·+k(k+2)+(k+1)((k+1)+2) = (k+1)((k+1)+1)(2(k+1)+7)
6
,
and this means the statement is true for n = k + 1.
Thus the result follows by mathematical induction.
■
279
9. For any integer n ≥ 0, it follows that 24 | (52n − 1).
Proof. The proof is by mathematical induction.
(1) For n = 0, the statement is 24 | (52·0 − 1). This is 24 | 0, which is true.
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
24 | (52k − 1). This means 52k − 1 = 24a for some integer a, and from this we
get 52k = 24a + 1. Now observe that
52(k+1) − 1 =
52k+2 − 1 =
5252k − 1 =
52(24a + 1) − 1 =
25(24a + 1) − 1 =
25 · 24a + 25 − 1 = 24(25a + 1).
This shows 52(k+1) − 1 = 24(25a + 1), which means 24 | 52(k+1) − 1.
This completes the proof by mathematical induction.
■
11. For any integer n ≥ 0, it follows that 3 | (n3 + 5n + 6).
Proof. The proof is by mathematical induction.
(1) When n = 0, the statement is 3 | (03 + 5 · 0 + 6), or 3 | 6, which is true.
(2) Now assume the statement is true for some integer n = k ≥ 0, that is assume
3 | (k3 + 5k + 6). This means k3 + 5k + 6 = 3a for some integer a. We need to
show that 3 | ((k + 1)3 + 5(k + 1) + 6). Observe that
(k + 1)3 + 5(k + 1) + 6 =
k3 + 3k2 + 3k + 1 + 5k + 5 + 6
=
(k3 + 5k + 6) + 3k2 + 3k + 6
=
3a + 3k2 + 3k + 6
=
3(a + k2 + k + 2).
Thus we have deduced (k + 1)3 − (k + 1) = 3(a + k2 + k + 2). Since a + k2 + k + 2 is
an integer, it follows that 3
| ((k + 1)3 + 5(k + 1) + 6).
It follows by mathematical induction that 3 | (n3 + 5n + 6) for every n ≥ 0.
■
13. For any integer n ≥ 0, it follows that 6 | (n3 − n).
Proof. The proof is by mathematical induction.
(1) When n = 0, the statement is 6 | (03 − 0), or 6 | 0, which is true.
280
Solutions
(2) Now assume the statement is true for some integer n = k ≥ 0, that is, assume
6 | (k3 − k). This means k3 − k = 6a for some integer a. We need to show that
6 | ((k + 1)3 − (k + 1)). Observe that
(k + 1)3 − (k + 1) =
k3 + 3k2 + 3k + 1 − k − 1
=
(k3 − k) + 3k2 + 3k
=
6a + 3k2 + 3k
=
6a + 3k(k + 1).
Thus we have deduced (k + 1)3 − (k + 1) = 6a + 3k(k + 1). Since one of k or (k + 1)
must be even, it follows that k(k + 1) is even, so k(k + 1) = 2b for some integer
b. Consequently (k + 1)3 − (k + 1) = 6a + 3k(k + 1) = 6a + 3(2b) = 6(a + b). Since
(k + 1)3 − (k + 1) = 6(a + b) it follows that 6 | ((k + 1)3 − (k + 1)).
Thus the result follows by mathematical induction.
■
15.
1
If n ∈ N, then 1·2 + 1
2·3 + 1
3·4 + 1
4·5 + · · · +
1
n(n+1) = 1 − 1
n+1 .
Proof. The proof is by mathematical induction.
1
1
(1) When n = 1, the statement is 1(1+1) = 1 − 1
1+1 , which simplifies to 2 = 1
2 .
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
1
1·2 + 1
2·3 + 1
3·4 + 1
4·5 + · · · +
1
k(k+1) = 1 − 1
k+1 . Next we show that the statement for
n = k + 1 is true. Observe that
1
1
1
1
1
1
+
+
+
+ · · · +
+
=
1 · 2
2 · 3
3 · 4
4 · 5
k(k + 1)
(k + 1)((k + 1) + 1)
µ
1
1
1
1
1
¶
1
+
+
+
+ · · · +
+
=
1 · 2
2 · 3
3 · 4
4 · 5
k(k + 1)
(k + 1)(k + 2)
µ
1 ¶
1
1 −
+
=
k + 1
(k + 1)(k + 2)
1
1
1 −
+
=
k + 1
(k + 1)(k + 2)
k + 2
1
1 −
+
=
(k + 1)(k + 2)
(k + 1)(k + 2)
k + 1
1 −
=
(k + 1)(k + 2)
1
1 −
=
k + 2
1
1 −
.
(k + 1) + 1
1
This establishes
,
1·2 + 1
2·3 + 1
3·4 + 1
4·5 + · · · +
1
(k+1)((k+1)+1 = 1 −
1
(k+1)+1 which is to say
that the statement is true for n = k + 1.
This completes the proof by mathematical induction.
■
281
17. Suppose A1, A2,... An are sets in some universal set U, and n ≥ 2. Prove that
A1 ∩ A2 ∩ ··· ∩ An = A1 ∪ A2 ∪ ··· ∪ An.
Proof. The proof is by strong induction.
(1) When n = 2 the statement is A1 ∩ A2 = A1 ∪ A2. This is not an entirely
obvious statement, so we have to prove it. Observe that
A1 ∩ A2
=
{x : (x ∈ U) ∧ (x ∉ A1 ∩ A2)} (definition of complement)
=
{x : (x ∈ U)∧ ∼ (x ∈ A1 ∩ A2)}
=
{x : (x ∈ U)∧ ∼ ((x ∈ A1) ∧ (x ∈ A2))} (definition of ∩)
=
{x : (x ∈ U) ∧ (∼ (x ∈ A1)∨ ∼ (x ∈ A2))} (DeMorgan)
=
{x : (x ∈ U) ∧ ((x ∉ A1) ∨ (x ∉ A2))}
=
{x : (x ∈ U) ∧ (x ∉ A1) ∨ (x ∈ U) ∧ (x ∉ A2)} (distributive prop.)
=
{x : ((x ∈ U) ∧ (x ∉ A1))} ∪ {x : ((x ∈ U) ∧ (x ∉ A2))} (def. of ∪)
=
A1 ∪ A2 (definition of complement)
(2) Let k ≥ 2. Assume the statement is true if it involves k or fewer sets. Then
A1 ∩ A2 ∩ ··· ∩ Ak−1 ∩ Ak ∩ Ak+1 =
A1 ∩ A2 ∩ ··· ∩ Ak−1 ∩ (Ak ∩ Ak+1) = A1 ∪ A2 ∪ ··· ∪ Ak−1 ∪ Ak ∩ Ak+1
=
A1 ∪ A2 ∪ ··· ∪ Ak−1 ∪ Ak ∪ Ak+1
Thus the statement is true when it involves k + 1 sets.
This completes the proof by strong induction.
■
19.
Pn
Prove
1/k2 ≤ 2 − 1/n
k=1
for every n.
Proof. This clearly holds for n = 1. Assume it holds for some n ≥ 1. Then
Pn+1 1/k2 ≤ 2−1/n+1/(n+1)2 = 2− (n+1)2−n
k=1
n(n+1)2 ≤ 2 − 1/(n + 1). The proof is complete.
■
21.
1
If n ∈ N, then 1 + 12 + 13 + · · · + 1
2n ≥ 1 + n
2 .
Proof. If n = 1, the result is obvious.
Assume the proposition holds for some n > 1. Then
1
1
1
1
µ 1
1
1
1 ¶
µ
1
1
1
1 ¶
+
+
+ · · · +
=
+
+
+ · · · +
+
+
+
+ · · · +
1
2
3
2n+1
1
2
3
2n
2n + 1
2n + 2
2n + 3
2n+1
µ
¶
³
n ´
1
1
1
1
≥
1 +
+
+
+
+ · · · +
.
2
2n + 1
2n + 2
2n + 3
2n+1
³
1
Ńow, the sum 2n+1 + 1
2n+2 +
1
2n+3 + · · · +
1
2n+1
on the right has 2n+1 −2n = 2n terms,
1
all greater than or equal to 2n+1 , so the sum is greater than 2n 1
2n+1 = 1
2 . Therefore
1
³
´
¢
1<
br />
¢
we get 1 + 12 + 13 + · · · + 1
+
≥ ¡1 + n + 1
2n+1 ≥ ¡1 + n
2
2n+1 +
1
2n+2 +
1
2n+3 + · · · +
1
2n+1
2
2 =
1 + n+1
2 . This means the result is true for n + 1, so the theorem is proved.
■
282
Solutions
23.
¡n¢
Use induction to prove the binomial theorem (x + y)n = Pn
xn−i yi
i=0 i
.
Proof.
¢
¢
Notice that when n = 1, the formula is (x + y)1 = ¡1 x1 y0
x0 y1
0
+ ¡11
= x + y,
which is true.
Now assume the theorem is true for some n > 1. We will show that this implies
that it is true for the power n + 1. Just observe that
(x + y)n+1
=
(x + y)(x + y)n
n à !
n
X
=
(x + y)
xn−i yi
i
i=0
n à !
Ã
!
n
n
n
X
X
=
x(n+1)−i yi +
xn−i yi+1
i
i
i=0
i=0
n "Ã !
Ã
!#
n
n
X
=
+
x(n+1)−i yi
+ yn+1
i
i
i=0
− 1
n Ã
!
Ã
!
n
n
X
+ 1
+ 1
=
x(n+1)−i yi
+
yn+1
i
n
i=0
+ 1
n+1 Ã
!
n
X
+ 1
=
x(n+1)−i yi.
i
i=0
This shows that the formula is true for (x + y)n+1, so the theorem is proved.
■
25. Concerning the Fibonacci sequence, prove that F1+F2+F3+F4+...+Fn = Fn+2−1.
Proof. The proof is by induction.
(1) When n = 1 the statement is F1 = F1+2 − 1 = F3 − 1 = 2 − 1 = 1, which is true.
Also when n = 2 the statement is F1 + F2 = F2+2 − 1 = F4 − 1 = 3 − 1 = 2, which is
true, as F1 + F2 = 1 + 1 = 2.
(2) Now assume k ≥ 1 and F1 + F2 + F3 + F4 + . . . + Fk = Fk+2 − 1. We need to show
F1 + F2 + F3 + F4 + ... + Fk + Fk+1 = Fk+3 − 1. Observe that
F1 + F2 + F3 + F4 + ... + Fk + Fk+1 =
(F1 + F2 + F3 + F4 + ... + Fk) + Fk+1 =
Fk+2 − 1 + +Fk+1 = (Fk+1 + Fk+2) − 1
=
Fk+3 − 1.
This completes the proof by induction.
■
27. Concerning the Fibonacci sequence, prove that F1 + F3 + ··· + F2n−1 = F2n.
Proof. If n = 1, the result is immediate. Assume for some n > 1 we have
Pn
F
Pn+1 F
F
i=1
2i−1 = F2n. Then
i=1
2i−1 = F2n+1+Pn
Book of Proof Page 40