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

Solution 1:

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.

Solution 2:

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$