Previous: Homework assignment 03Homework assignment 03 Up: Homework assignmentsHomework assignments Next: Homework assignment 06Homework assignment 06
Document also available in PDF, Postscript, DVI, pure text and LaTeX.

Homework assignment 04



2.2. Induction

Exercise 1  [30 p. 108]   Prove that n!>= 2n-1 for n>= 1.
Proof: [Correction] The first step, is to check the base case. From table ??, it is clear that it works for the first couple of values. Now, let's take an integer k>= 2, and assume (k-1)! >= 2(k-1)-1= 2k-2. The following proves that k!>= 2k-1:
k! = k×(k-1)!
  >= k×2k-2   (by the induction hypothesis)
  >= 2×2k-2   (since k>=2)
  = 2k-1
Conclusion: by induction, n! >= 2n-1.
n 2n-1 n!
1 1 1
2 2 2
3 4 6
4 8 24
5 16 120
6 32 720
: : :

Table 1: Table of 2n-1 and n! for n>= 1.

Exercise 2  [31 p. 108]   Prove that n!<nn for n>= 2.
Proof: [Correction] The first step, is to check the base case (see table ??). Now, let's take be an integer k>=3, and assume (k-1)! < (k-1)(k-1). The following proves that k! < kk:
k! = k×(k-1)!
  < k×(k-1)(k-1)   (by the induction hypothesis)
  < k× k(k-1)
  = kk
Conclusion: by induction n!<nn for all n>=2

n n! nn
2 2 4
3 6 27
4 24 256
5 120 3125
6 720 46656
7 5040 823543
: : :

Table 2: Table of n! and nn for n >= 2.

Exercise 3  [32 p. 108]   Prove that (1+x)n>1+xn for n>1, x>0.
Proof: [Correction] We assume ninZ and xinR. Let x be a fixed real number. We will prove the result by induction on n.

The base case for n=2 clearly holds, since (1+x)2=1+2x+x2>1+x2. We now take an integer k>2, and assume (1+x)(k-1)>1+x(k-1), and show that (1+x)k>1+xk:
(1+x)k = (1+x)×(1+x)(k-1)
  > (1+x)×(1+x(k-1))   (by the induction hypothesis)
  = 1 + x + x(k-1) + xk   (since, x+x(k-1)>0)
  > 1 + xk
Conclusion: (1+x)k > 1+xk.

Exercise 4  [38 p. 108]   Prove 7n-2n is divisible by 5.
Proof: [Correction] As a base, we can take n=0 to get 70-20=1-1=0, which is obviously divisible by 5. We now take an integer k>0, and assume 7k-1-2k-1 = 5m for some integer m, otherwise said, 7k-1 = 5m+2k-1. We can prove that 7k-2k is also divisible by 5 as follow:
7k-2k
= 7 ( 7k-1 ) -2k
 
= 7 ( 5m+2k-1 ) -2k
  (by the induction hypothesis)
 
= 5(7m)+7 ( 2k-1 ) -2 ( 2k-1 )
 
= 5(7m)+5 ( 2k-1 )
 
= 5 ( 7m + 2k-1 )
Since 7m + 2k-1 is an integer, 7k-2k is divisible by 5, which concludes the proof.

Exercise 5  [57 p. 110]   What is wrong with the following ``proof'' by mathematical induction? We will prove that all computers are built by the same manufacturer. In particular, we will prove that in any collection of n computers where n is a positive integer, all of the computers are built by the same manufacturer. We first prove P(1), a trivial process, because in any collection consisting of one computer, there is only one manufacturer. Now we assume P(k); that is, in any collection of k computers, all the computers were built by the same manufacturer. To prove P(k+1), we consider any collection of k+1 computers. Pull one of these k+1 computers (call it HAL) out of the collection. By our assumption, the remaining k computers all have the same manufacturer. Let HAL change places with one of these k computers. In the new group of k computers, all have the same manufacturer. Thus, HAL's manufacturer is the same one that produced all the other computers, and all k+1 computers have the same manufacturer.
Proof: [Correction] The induction step just does not work for n=2!

Exercise 6  [62 p. 110]   Prove that any amount of postage greater than or equal to 12 cents can be built using only 4-cent and 5-cent stamps.
Proof: [Correction] To prove the above by induction, we start with the base cases.
12 = 4(3)
13 = 4(2)+5
14 = 4(1)+5(2)
15 = 5(3)
Now we take an integer k>15 and assume P(r) holds for any integer r such that 12<= r<k. In particular, P(k-4) will hold. I.e., you can build k-4 using 4 cents and 5 cents. By adding a stamp of 4 cents, you get k, so P(k) also holds.

Conclusion: by the second principle of induction, P(k) holds for any integer k>=12.

Alternatively, we can give an explicit construction of all possible amounts of postage. Such that, if mod(k,4)=0 then the postage can be composed completely out of 4-cent stamps. Else if mod(k,4) = 1, then the postage can be composed out of k-1/4 4-cent stamps and one 5-cent stamp. Likewise, if mod(k,4)=2, then the postage can be composed out of k-2/4 4-cent stamps and two 5-cent stamps. Finally, if mod(k,4)=3, then we can get the exact postage k by taking k-3/4 4-cent stamps and three 5-cent stamps.
Previous: Homework assignment 03Homework assignment 03 Up: Homework assignmentsHomework assignments Next: Homework assignment 06Homework assignment 06
Homework assignment 04 / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:28 2003