Prove that $(1-p^n)^m + (1 - q^m)^n \geq 1$

Question

Prove that $(1-p^n)^m + (1 - q^m)^n \geq 1$ for positive integers $m,n$ and $p,q \in (0,1)$ such that $p+q=1$.

The idea is that $1-p^n$ may be interpreted as the probability of $n$ failures in $n$ Bernoulli trials with the probability of success $p$. Similarly, $1-q^m$ is the probability of $m$ failures in $m$ Bernoulli trials with the probability of success $q$. Essentially, since $p+q = 1$ you may think as having one coin with a bias $p$. But the crucial trick is contained in the answer below, pointed out by @william122

Have you tried solving this problem by yourself? Please show your steps and which are in specific the reasons you cannot do it. — johnny09, Dec 20 '18 at 23:22
Yep, I was also thinking about tossing a biased coin several times, as @william122 does in his answer below. But I didn't think about a grid which is a nice idea. — dkalocinski, Dec 20 '18 at 23:24
Duplicate of If $p + q = 1$ prove that for any natural $n, m$ following is true: $(1 - p^n)^m + (1 - q^m)^n \ge 1$ — Sil, Oct 11 '20 at 18:52

score 11 · Answer 1 · answered Dec 20 '18 at 23:17

11

Consider a coin which flips head with probability $p$ and tails with $q$. Now, flip an $m$ by $n$ grid of such coins. Clearly, the probability that all columns contain at least one tail is $(1-p^n)^m$, and the probability all rows contain at least one head is $(1-q^m)^n$. However, suppose the first condition is not true. Then, there exists a column with only heads, so the second one must be. Likewise if the second is false, so at least one of these conditions must be met, and their probabilities add to at least 1.

answered Dec 20 '18 at 23:17

william122

609

It's as if this problem was contrived to lead to such an elegant solution. – Display name Dec 20 '18 at 23:22
How to explain in simple words that the probabilities of these two conditions add to at least $1$? – dkalocinski Dec 20 '18 at 23:36
1

So, we have two events. As one will always occur, these two probabilities must cover all cases, so the sum of them is at least 1 – william122 Dec 20 '18 at 23:37
Of course, sorry, it follows from your answer @william122 – dkalocinski Dec 20 '18 at 23:38

Prove that $(1-p^n)^m + (1 - q^m)^n \geq 1$

1 Answers1