We have to prove the inequality
, for all integers k such as
We use the mathematical induction.
, which is true.
Suppose is true and we prove that is also true.
We have:
Here's another idea. For each , let denote a random variable which takes the value with probability , and the value otherwise. Suppose moreover that these random variables are independent. Then is the probability that all of the take the value , hence is the probability that not all of the take on the value , i.e. that at least one of them take the value . This is clearly less than .