15
$\begingroup$

I would like to prove the following inequality. It arises from my study of random matrices. I have verified the inequality for $q\in \{0.01,0.02, \ldots, 0.99\}$ and $1\le n\le 100$.

Let $n$ be any positive integer and $0\le q\le 1$. Then the following inequality is true. $$\sum_{k=0}^n(-1)^k\binom{n}{k}(q^k-q^n)^n\le (1-q^n)^n.$$

I suspect that the Wilf-Zeilberger method applies here. But I can't get it to work.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Is this an inclusion-exclusion sum? $\endgroup$
    – Brendan McKay
    Commented Jun 26, 2021 at 10:02
  • $\begingroup$ @BrendanMcKay: Yes, you are right. The post below by Fedor clarifies what the inclusion-exclusion sum is about. – shortfatboy $\endgroup$
    – shortfatboy
    Commented Jun 26, 2021 at 14:56
  • 4
    $\begingroup$ More generally, for integer $m,n\geq 0$ we have $$\sum_{k=0}^n(-1)^k\binom{n}{k}(q^k-q^n)^m\le (1-q^m)^n.$$ $\endgroup$
    – Max Alekseyev
    Commented Jun 26, 2021 at 16:03

2 Answers 2

Reset to default
21
$\begingroup$

Mark each box of an $n\times n$ table with probability $q$. By inclusion-exclusion the difference RHS-LHS equals to the probability that there exists a full row (with all boxes marked) but there does not exist a full column: that's because for given $k$ rows the probability that (they are full but no column is full) equals $(q^k-q^n)^n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, @FedorPetrov! You are right! Indeed, the LHS is equal to the probability that there does not exist a full row nor a full column, while the RHS is equal to the probability that there does not exist a full column. Clearly, LHS is at most RHS. $\endgroup$
    – shortfatboy
    Commented Jun 26, 2021 at 14:46
  • 2
    $\begingroup$ See also Stanley, Enumerative Combinatorics Vol. 1 (2nd edition), Exercise 2.25(a). $\endgroup$
    – Sam Hopkins
    Commented Jun 26, 2021 at 15:25
  • 2
    $\begingroup$ And a previous MO question: mathoverflow.net/questions/125919/… $\endgroup$
    – Sam Hopkins
    Commented Jun 26, 2021 at 15:30
3
$\begingroup$

Mathematica suggests that $$ \sum_{k=0}^n (-1)^k \binom{n}{k} \left( \frac{q^k-q^n}{1-q^n} \right)^n = 1-n q^n + n^2 O(q^{2n-1}) + O(q^{2n}) $$ You can try to expandin $(q^k-q^n)^n$ using the binomial theorem, and then try to change order of the sums.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .