Mathematical induction problems with solutions

Practice problems Solutions
1. Induction proofs, type I: Sum/product formulas: The most common, and the easiest, application of
induction is to prove formulas for sums or products of n terms. All of these proofs follow the same pattern.
(a)
Pn
i=1 i(i + 1) = n(n+1)(n+2)
3
(b)
Pn
i=0 2i = 2n+1 􀀀 1 (sum of powers of 2)
(c)
Pn
i=0 ri = 1􀀀rn+1
1􀀀r (r 6= 1) (sum of nite geometric series)
(d)
Pn
i=0 i!i = (n + 1)! 􀀀 1.
Solution: All proofs follow the pattern illustrated by the sample proof (of the formula
Pn
i=1 i = n(n+1)=2). We
will carry out the details for (a) and (d). The other formulas can be proved similarly. (Note that (b) is a special
case of (c).)
Proof of (a): We seek to show that, for all n 2 N,
( )
Xn
i=1
i(i + 1) =
n(n + 1)(n + 2)
3
:
Base case: When n = 1, the left side of ( ) is 1 (1 + 1) = 2, and the right side is 1 (1 + 1)(1 + 2)=3 = 2, so both
sides are equal and ( ) is true for n = 1.
Induction step: Let k 2 N be given and suppose ( ) is true for n = k. Then
kX+1
i=1
i(i + 1) =
Xk
i=1
i(i + 1) + (k + 1)(k + 2)
=
k(k + 1)(k + 2)
3
+ (k + 1)(k + 2) (by induction hypothesis)
=
(k + 1)(k + 2)(k + 3)
3
:
Thus, ( ) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of induction, it follows that ( ) is true for all n 2 N.
Proof of (d): We seek to show that, for all n 2 N,
( )
Xn
i=0
i!i = (n + 1)! 􀀀 1:
Base case: When n = 1, the left side of ( ) is 0 + 1 1! = 1, and the right side is (1 + 1)! 􀀀 1 = 1, so both sides are
equal and ( ) is true for n = 1.
Induction step: Let k 2 N be given and suppose ( ) is true for n = k. Then
kX+1
i=1
i i! =
Xk
i=1
i i! + (k + 1)(k + 1)!
= (k + 1)! 􀀀 1 + (k + 1)(k + 1)! (by induction hypothesis)
= (k + 1)!(k + 2) 􀀀 1
= (k + 2)! 􀀀 1:
Thus, (2) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of induction, ( ) is true for all n 2 N.
2. Induction proofs, type II: Inequalities: A second general type of application of induction is to prove
inequalities involving a natural number n. These proofs also tend to be on the routine side; in fact, the
algebra required is usually very minimal, in contrast to some of the summation formulas.
In some cases the inequalities don't \kick in" until n is large enough. By checking the rst few values of n
one can usually quickly determine the rst n-value, say n0, for which the inequality holds. Induction with
n = n0 as base case can then be used to show that the inequality holds for all n > n0.
1
Math 347 Worksheet: Induction Proofs, I|Solutions A.J. Hildebrand
(a) 2n > n
(b) 2n n2 (n 4)
(c) n! > 2n (n 4)
(d) (1 􀀀 x)n 1 􀀀 nx (0 < x < 1)
(e) (1 + x)n 1 + nx (x > 0)
Solution: We will give detailed proofs for (c), (d), (e). The other inequalities can be proved similarly.
Proof of (c): A direct check of the inequality for the rst few values of n shows that the left-right pairs in the stated
inequality are (1; 2); (2; 4); (6; 8); (24; 16); (120; 32). Thus, the inequality fails for n = 1; 2; 3, but holds for n = 4; 5.
This suggests that it indeed holds for all n from 4 onwards. We will prove this by induction, i.e., we will show that
( ) n! > 2n
holds for all n 4.
Base case: For n = 4, the left and right sides of ( ) are 24 and 16, respectively, so ( ) is true in this case.
Induction step: Let k 4 be given and suppose ( ) is true for n = k. Then
(k + 1)! = k!(k + 1)
> 2k(k + 1) (by induction hypothesis)
2k 2 (since k 4 and so k + 1 2))
= 2k+1:
Thus, ( ) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of induction, it follows that ( ) is true for all n 4.
Proof of (d) and (e): We will prove that for any real number x > 􀀀1
( ) (1 + x)n 1 + nx:
holds for any n 2 N. This simultaneously proves both statements (d) and (e): (e) corresponds to the case x > 0,
while (d) corresponds to the case 􀀀1 < x < 0 (with x0 = 􀀀x in place of x).
Base case: For n = 1, the left and right sides of ( ) are both 1 + x, so ( ) holds.
Induction step: Let k 2 N be given and suppose ( ) is true for n = k and any real number x > 􀀀1. We seek to
show that ( ) holds for n = k + 1 and any real number x > 􀀀1.
Let x > 􀀀1 be given. Then
(1 + x)k+1 = (1 + x)k(1 + x)
(1 + kx)(1 + x) (by ind. hyp. and since x > 􀀀1 and thus (1 + x) > 0)
= 1 + (k + 1)x + kx2 (by algebra)
1 + (k + 1)x (since kx2 0):
Hence ( ) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of induction, it follows that ( ) holds for all n 2 N.
3. Induction proofs, type III: Extension of theorems from 2 variables to n variables: Another very
common and usually routine application of induction is to extend general results that have been proved for
the case of 2 variables to the case of n variables. Below are some examples. In proving these results, use
the case n = 2 as base case. To see how to carry out the general induction step (from the case n = k to
n = k + 1), it may be helpful to rst try to see how get from the base case n = 2 to the next case n = 3.
(a) Show that if x1; : : : ; xn are odd, then x1x2 : : : xn is odd. (Use the fact (proved earlier) that the product
of 2 odd numbers is odd, as starting point, and use induction to extend this result to the product of n
odd numbers.)
Solution: We will prove by induction on n the following statement:
P(n): If x1; : : : ; xn are odd numbers, then x1x2 : : : xn is odd.
We will use the following fact (proved earlier):
( ) If x and y are odd, then xy is odd.
Base case: For n = 1, the product x1 : : : xn reduces to x1, so is odd whenever x1 is odd. Hence P(1) is true.
Induction step.
2
Math 347 Worksheet: Induction Proofs, I|Solutions A.J. Hildebrand
Let k 1, and suppose P(k) is true, i.e., suppose that any product of k odd numbers is again odd.
We seek to show that P(k + 1) is true, i.e., that any product of k + 1 odd numbers is odd.
Let x1; : : : ; xk+1 be odd numbers.
Applying the induction hypothesis to x1; : : : ; xk, we obtain that the product x1x2 : : : xk is odd.
Since xk+1 is odd and, by ( ), the product of two odd numbers is again odd, it follows that x1x2 : : : xk+1 =
(x1 : : : xk)xk+1 is odd.
As x1; : : : ; xk+1 were arbitrary odd numbers, we have proved P(k + 1), so the induction step is complete.
Conclusion: By the principle of induction, it follows that P(n) is true for all n 2 N.
(b) Show that if ai and bi (i = 1; 2; : : : ; n) are real numbers such that ai bi for all i, then
Xn
i=1
ai
Xn
i=1
bi:
(Use the fact (from Chapter 1) that a b and c d implies a + c b + d.)
Solution: We will prove by induction on n the following statement:
P(n): For all real numbers ai and bi (i = 1; : : : ; n) such that ai bi for all i we have
( )
Xn
i=1
ai
Xn
i=1
bi:
(Note that the quanti er \for all real numbers ai and bi" must be part of the induction statement we seek to
prove.)
Base case: For n = 1, the left and right sides are a1 and b1, respectively, and the inequality ( ) therefore follows
from our hypothesis that ai bi for all i = 1; : : : ; n. Hence P(1) is true.
Induction step:
Let k 1, and suppose P(k) is true, i.e., suppose that for n = k and any choice of real numbers a1; : : : ; ak
and b1; : : : ; bk satisfying ai bi for each i, the inequality ( ) holds.
We seek to show that P(k + 1) is true, i.e., that for n = k + 1 any choice of real numbers a1; : : : ; ak+1 and
b1; : : : ; bk+1 satisfying ai bi for each i, the inequality ( ) holds.
Let a1; : : : ; ak+1 and b1; : : : ; bk+1 be given real numbers such that ai bi for each i.
Then
kX+1
i=1
ai =
Xk
i=1
ai + ak+1

Xk
i=1
bi + ak+1 (by induction hypothesis applied to a1; : : : ak)

Xk
i=1
bi + bk+1 (by assumption ak+1 bk+1)
=
kX+1
i=1
bi:
Thus, ( ) holds for n = k + 1 and the given numbers a1; : : : ; ak+1 and b1; : : : ; bk+1.
Since the a1; : : : ; ak+1 and b1; : : : ; bk+1 were arbitrary real numbers satisfying ai bi for each i, we have
obtained statement P(k + 1), and the proof of the induction step is complete.
Conclusion: By the principle of induction, it follows that P(n) is true for all n 2 N.
(c) Show that if x1; : : : ; xn are real numbers, then

sin

Xn
i=1
xi
!
Xn
i=1
jsin xij :
(Use the trig identity for sin( + ).)
3
Math 347 Worksheet: Induction Proofs, I|Solutions A.J. Hildebrand
Solution: We seek to prove by induction on n the following statement:
P(n): For all real numbers x1; : : : ; xn we have
( )

sin

Xn
i=1
xi
!
Xn
i=1
jsin xij :
The key to the argument is the trig identity
sin( + ) = sin cos + sin cos ;
which is valid for any real and . Since j cos xj 1, this identity implies, via the triangle inequality,
( ) j sin( + )j j sin cos j + j sin cos j
j sin j + j sin j:
The inequality ( ) is the case n = 2 of the statement ( ) we seek to prove, and will be needed in the induction
proof. (One could also use it as the base case of an induction proof that starts with n = 2, but it is easier to
start the induction with n = 1, where the base case is trivial.)
Base case: For n = 1, the left and right sides of ( ) are both equal to j sin x1j, so ( ) holds trivially in this case.
Hence P(1) is true.
Induction step:
Let k 1, and suppose P(k) is true, i.e., suppose that ( ) holds for n = k and any choice of real numbers
x1; : : : ; xk.
We seek to show that P(k + 1) is true, i.e., that for any choice of real numbers x1; : : : ; xk+1 the inequality
( ) holds.
Let x1; : : : ; xk+1 be given real numbers.
Then

sin

kX+1
i=1
xi
! =

sin
 
Xk
i=1
xi
!
+ xk+1
!


sin

Xk
i=1
xi
! + jsin xk+1j (by ( ) with =
Xk
i=1
xi and = xk+1)

Xk
i=1
jsin xij + jsin xk+1j (by induction hypothesis applied to x1; : : : ; xk)
=
kX+1
i=1
jsin xij :
Thus, ( ) holds for n = k + 1 and the given numbers x1; : : : ; xk+1.
Since the x1; : : : ; xk+1 were arbitrary real numbers, we have obtained statement P(k +1), and proof of the
induction step is complete.
Conclusion: By the principle of induction, it follows that P(n) is true for all n 2 N.
(d) Show that if A1; : : : ;An are sets, then
(A1 [ [ An)c = Ac
1 \ \ Ac
n:
(This is a generalization of De Morgan's Law to unions of n sets. Use De Morgan's Law for two sets
((A [ B)c = Ac \ Bc) and induction to prove this result.)
Solution: We seek to prove by induction on n the following statement:
P(n): For all sets A1; : : : ;An we have
( ) (A1 [ [ An)c = Ac
1 \ \ Ac
n:
The key to the argument is two set version of De Morgan's Law:
( ) (A [ B)c = Ac \ Bc;
which holds for any sets A and B.
Base case: For n = 1, the left and right sides of ( ) are both equal to Ac
1, so ( ) holds trivially in this case.
Hence P(1) is true.
Induction step:
4
Math 347 Worksheet: Induction Proofs, I|Solutions A.J. Hildebrand
Let k 1, and suppose P(k) is true, i.e., suppose that ( ) holds for n = k and any sets A1; : : : ;Ak.
We seek to show that P(k + 1) is true, i.e., that for any sets A1; : : : ;Ak+1, ( ) holds.
Let A1; : : : ;Ak+1 be given sets.
Then
(A1 [ [ Ak+1)c = ((A1 [ [ Ak) [ Ak+1)c
= (A1 [ [ Ak)c \ Ac
k+1 (by ( ) with A = (A1 [ [ Ak) and B = Ak+1)
= (Ac
1 \ \ Ac
k) \ Ac
k+1 (by induction hypothesis applied to A1; : : : ;Ak)
= Ac
1 \ \ Ac
k \ Ac
k+1:
Thus, ( ) holds for n = k + 1 and the given sets A1; : : : ;Ak+1.
Since the A1; : : : ;Ak+1 were arbitrary sets, we have obtained statement P(k + 1), and the proof of the
induction step is complete.
Conclusion: By the principle of induction, it follows that P(n) is true for all n 2 N.
5