Mathematicians do like giving proofs of known results from some specific point of view.

Here goes the combinatorial proof of the inequality

To be precise, I define our heroes. is a length of a half-circle of the unit radius, and is the common point of the segments

The idea is that for a positive integer and a complex , , we have

The latter inequality is obtained by multiplying the definitive inequalities for

We apply it for , the primitive root of unity of degree .

Note that since the chord of the unit circle joining 1 and is shorter than the arc between these two points (which equals , since the whole circle is a union of congruent arcs.)

We have

On the other hand, since and is the complex conjugate to for , we get

Thus that yields (1) as would grow exponentially fast if .

Well, if you really prefer combinatorial proofs, here is a variant of the above argument for you. Although I do not provide any combinatorial quantity counted by (that what we expect from a combinatorial proof of inequality (1)), I instead do this for something like .

Count the number of permutations of for which the number of inversions is divisible by . Since

is a generating polynomial for the number of permutations with the given number of inversions, by the polarization formula

for we get

If , we see that the summands corresponding to are negative reals provided that (this follows from evaluating the argument of , which equals , and summing over : we get that is modulo for ). By absolute value they are exponentially greater both than (which corresponds to , see the explanation above) and all other summands (since say for other roots, and is either 0 or the same as . So we get that is absurd.

### Like this:

Like Loading...

## Leave a comment