# Motivating combinatorics identity to different audiences: $\binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1}$

Recently I asked the following identity on Math.StackExchange knowing it had several proofs:

$$\binom{n}{k}^2 \geq \binom{n}{k-1}\binom{n}{k+1}$$

See here. They quickly give the one-liner:

In your initial inequality divide the left hand side by the right hand side and simplify.

This is kind of a proof. It works on math.SE since many people know combinatorics there.
Probably they meant:

Using the identity $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ and cross multiplying, the identity is equivalent to: $$k!^2 (n-k)!^2 \leq (k-1)!(k+1)! (n-k-1)! (n-k+1)!$$

Let's try proving: $k!^2 \geq (k-1)!(k+1)!$ Dividing both sides by $k!^2$ we get $1 \leq \frac{k+1}{k-1}$ which is true.

A similar proof works for the factors of $(n-k)!$

Overall, people had no idea where I was coming from. I had been reading a Richard Stanley article about log-concave sequence of numbers and I was hoping to digest it for my class. The logic made sense to me:

• Instead of clearing denominators every single time (which maybe neither exciting nor informative), why not exploit the that $a_n^2 \geq a_{n-1}a_{n+1}$ for this particular sequence of numbers?

Eventually two other proofs surfaced using other branches of math, but I still don't feel like I got any point across.

In fact, how do I motivate even this one proof? Is this equation really that obvious that it only deserves one sentence?

• In your second highlighted section, you have not actually given a proof. As a small correction, immediately after Let's try proving the inequality sign should be switched. Then divide both sides by $k!^2$ to get $1 \leq \frac{k+1}{k} = 1 + \frac{1}{k}$. More seriously: You have shown that the identity leads to a true fact; really what you need to do is show these are all iff statements. (Or to start with a true fact and then derive the identity in question). Commented Jun 17, 2014 at 0:39

Does this help?

$(k-1)!(k+1)! = (\frac{k!}{k})(k!(k+1)) = k!^2\frac{k+1}{k} \ge k!^2\frac{k}{k}=k!^2$

and for $(n-k)!$ define $a=(n-k)$ and use the same trick.

Another way would be to note that ${n\choose{k-1}} = \frac{1}{k}{n\choose{k}}$ and that ${n\choose{k+1}} = k{n\choose{k}}$

• [This is of course the same derivation I posted in my comment, except that you factor out a $k!^2$ rather than dividing both sides by it.] Commented Jun 18, 2014 at 21:56
• Of course, I just propose it might be clearer this way. Commented Jun 18, 2014 at 21:59
• I think what would be great is if someone could come up with a counting argument; that is, a way of thinking about each side of the identity as counting something, so that the result clearly holds. Nothing comes to (my) mind yet... Commented Jun 18, 2014 at 22:04
• [FWIW: Down-voter is not me...] Commented Jun 18, 2014 at 23:24
• @BenjaminDickman that's ok I couldn't care less about rep. Commented Jun 19, 2014 at 0:58

It depends on the audience... I (and you, clearly) don't need more; my second year students (struggling with basic factorial identities and such) need a lot more handholding.

Question then is how to do the handholding. I have found that it is helpful to state what proof technique will be used (even if "obvious" from the proof itself), and write out most steps, even if rather simple algebra. If on the blackboard, you can skimp steps, but be prepared to fill in when asked (and you end up spending more time that way). This helps when fine-tuning.