326 Methods of Proof10.Assume the contrary. Our chosen numbersa 1 ,a 2 ,...,ak+ 1 must have a total of at
mostkdistinct prime factors (the primes less than or equal ton). Letop(q)denote the
highest value ofdsuch thatpd|q. Also, leta =a 1 a 2 ···ak+ 1 be the product of the
numbers. Then for each primep,op(a)=∑k+ 1
i= 1 op(ai), and it follows that there can
be at most onehostilevalue ofifor whichop(ai)>op 2 (a). Because there are at most
kprimes that dividea, there is someithat is not hostile for any such prime. Then
2 op(ai)≤op(a),soop(ai)≤op(aai)for each primepdividinga. This implies thatai
dividesaai, which contradicts the fact that theaidoes not divide the product of the other
aj’s. Hence our assumption was false, and the conclusion follows.
(Hungarian Mathematical Olympiad, 1999)
11.The base casen=1is^12 = 1 −^12 , true. Now the inductive step. The hypothesis
is that
1
k+ 1+
1
k+ 2+···+
1
2 k= 1 −
1
2
+···+
1
2 k− 1−
1
2 k.
We are to prove that
1
k+ 2+···+
1
2 k+
1
2 k+ 1+
1
2 k+ 2= 1 −
1
2
+···−
1
2 k+
1
2 k+ 1−
1
2 k+ 2.
Using the induction hypothesis, we can rewrite this as
1
k+ 2+···+
1
2 k+
1
2 k+ 1+
1
2 k+ 2
=1
k+ 1+
1
k+ 2+···+
1
2 k+
1
2 k+ 1−
1
2 k+ 2,
which reduces to
1
2 k+ 2=
1
k+ 1−
1
2 k+ 2,
obvious. This completes the induction.
12.The base case is trivial. However, as I.M. Vinogradov once said, “it is the first
nontrivial example that matters.’’ And this isn=2, in which case we have|sin 2x|= 2 |sinx||cosx|≤ 2 |sinx|.This suggests to us to introduce cosines as factors in the proof of the inductive step.
Assuming the inequality forn=k, we can write
|sin(k+ 1 )x|=|sinkxcosx+sinxcoskx|≤|sinkx||cosx|+|sinx||coskx|
≤|sinkx|+|sinx|≤k|sinx|+|sinx|=(k+ 1 )|sinx|.