# If $p + q = 1$ prove that for any natural $n, m$ following is true: $(1 - p^n)^m + (1 - q^m)^n \ge 1$

Let $p, q \in \mathbb R$ be positive reals for which $p + q = 1$. How to prove that for any two natural numbers $n, m$ the following inequality is true?

$(1 - p^n)^m + (1 - q^m)^n \ge 1$

I don't have a big knowledge about solving inequalities, so I tried to use cauchy-schwarz inequality, binomial theorem and some other baisc techniques, but it lead me nowhere. I've been thinking about it for a long time and now I'm completly stuck.

• Say us what you have attempted. – Jean Marie Dec 8 '16 at 17:15
• @J. Abraham I think must be solution with probability. – Michael Rozenberg Dec 8 '16 at 17:16
• Would you please put the question "off hold"? I've completed it with all the information. – J. Abraham Dec 8 '16 at 19:59
• This is another "missing context or other details" hold which I totally disagree with. To me, this is an interesting question and, as such, does not need any context. Let these questions go! – marty cohen Dec 8 '16 at 20:17
• tactical dot..... – james black Feb 8 '18 at 14:19

## Probability argument

Consider $m \times n$ grid (matrix if you like) with $m$ rows and $n$ columns, with either $0$ or $1$ numbers in its cells. Now let $p$ be probability that a cell contains $1$ and $q$ be probability that a cell contains $0$, so we have $p+q=1$.

Now what is the probability of (event $A$) each row having at least one $0$ in it? That is exactly the $P(A)=(1-p^n)^m$ ($p^n$ for a row made of $1s$, $1-p^n$ for row with at least one $0$, $(1-p^n)^m$ then for $m$ rows with this property). Similarly, probability of (event $B$) having in each column at least one $1$, is $(1-q^m)^n$. Thus we have

$$(1-p^n)^m+(1-q^m)^n = P(A) + P(B)$$

Now notice that $P(A \cup B) = 1$. This is because we will always have all rows containing a $0$ or all columns containing a $1$. If there would be for example no row containing a $0$, it would mean there is a row full of $1$s, which means all columns contain a $1$ (at least the one from the row which is filled with them). You can argue similarly for the case when there would be no column containing a $1$...

Another way to see this is to notice

$$P(A \cup B) = 1- P(\overline{A \cup B}) = 1- P(\overline{A} \cap \overline{B}) = 1$$

since $\overline{A}$ (having a row consisting only of $1s$) and $\overline{B}$ (having a row consisting only of $0$s) are clearly mutually exclusive, you can't have both at the same time, therefore $P(\overline{A} \cap \overline{B}) = 0$.

Putting all these together gives $$(1-p^n)^m+(1-q^m)^n = P(A) + P(B) = P(A \cup B) + P(A \cap B) \geq P(A \cup B) = 1$$

## Alternative solution - double induction

The problem 19 found here states and proves more general inequality using double induction:

$$(1-x_1 \dots x_n)^m + (1-y_1^m) \dots (1-y_n^m) \geq 1,\ x_i, y_i \in [0,1],\ x_i + y_i = 1.$$

You can just plug in the $x_i = p$, $y_i=q$ and reproduce the proof.

• Oh, I'm sorry I meant not $\le$ but $\ge$ – J. Abraham Dec 8 '16 at 18:20
• Inequality 19 is completely different than mine – J. Abraham Dec 9 '16 at 11:42
• @J.Abraham Have you tried the suggested substitution? $(1-p\dots p)^m = (1-p^n)^m$ and $(1-q^m)\dots (1-q^m) = (1-q^m)^n$. – Sil Dec 9 '16 at 11:50
• I understand but look again at the inequality at this site. It doesn't look like the one you wrote (the part with y) – J. Abraham Dec 9 '16 at 11:53
• Yea there was a mistake, but the referenced site still has it correct. Updated it here now. – Sil Dec 9 '16 at 11:53

Let there are two coins each with probability of head $p$. Let coin 1 has been tossed $n$ times independently and this whole scheme is repeated independently for $m$ times.

Similarly coin 2 is tossed $m$ times independently and this whole scheme is repeated independently for $n$ times and independently of coin 1.

$A$= at least one tail occurs in the string of 1st $n$-tosses, 2nd $n$ tosses, $\cdots$, $m^{th}$ $n$-tosses for coin 1

$B$= at least one head occurs in the string of 1st $m$-tosses, 2nd $m$ tosses, $\cdots$, $n^{th}$ $m$-tosses for coin 1

Notice the desired form is $P(A\cup B)\leq1$