6 1 Methods of Proof
g 0 (n)g 1 (n)···gk+ 1 (n)=g 0 (n)g 0 (n!)···gk(n!)<g 0 (n)(n!)g^0 (n!)g^1 (n!)···gk−^1 (n!)
< n(n!)g^1 (n)···gk(n)<(n·n!)g^1 (n)···gk(n)
<(nn)g^1 (n)···gk(n)=ng^0 (n)g^1 (n)···gk(n),completing this induction, and proving the claim.
Next, we show, also by induction onm, thatg 0 (n)g 1 (n)···gm(n)<fm+ 1 (n)for
alln. The base casem=1isn·n!<nn; it follows by multiplying 1· 2 <nand
3 · 4 ···n<nn−^2. Let’s see the inductive step. Using the inequality for thegm’s proved
above and the assumption that the inequality holds form=k, we obtain
g 0 (n)···gm(n)gm+ 1 (n)<ng^0 (n)···gm(n)<nfm+^1 (n)=fm+ 2 (n),which is the inequality form=k+1. This completes the last induction, and with it
the solution to the problem. No fewer than three inductions were combined to solve the
problem!
Listen and you will forget, learn and you will remember, do it yourself and you will
understand. Practice induction with the following examples.
- Prove for all positive integersnthe identity
1
n+ 1+
1
n+ 2+···+
1
2 n= 1 −
1
2
+
1
3
−···+
1
2 n− 1−
1
2 n.
12.Prove that|sinnx|≤n|sinx|for any real numberxand positive integern.
13.Prove that for any real numbersx 1 ,x 2 ,...,xn,n≥1,|sinx 1 |+|sinx 2 |+···+|sinxn|+|cos(x 1 +x 2 +···+xn)|≥ 1.14.Prove that 3n≥n^3 for all positive integersn.
15.Letn≥6 be an integer. Show that
(n
3)n
<n!<(n
2)n
.16.Letnbe a positive integer. Prove that1 +
1
23
+
1
33
+···+
1
n^3<
3
2
.
17.Prove that for any positive integernthere exists ann-digit number
(a) divisible by 2nand containing only the digits 2 and 3;
(b) divisible by 5nand containing only the digits 5, 6 , 7 , 8 ,9.