7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Benjamin Dickman Jun 17 '14 at 0:39
1
$\begingroup$

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}}$

$\endgroup$
  • $\begingroup$ [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.] $\endgroup$ – Benjamin Dickman Jun 18 '14 at 21:56
  • $\begingroup$ Of course, I just propose it might be clearer this way. $\endgroup$ – Bitwise Jun 18 '14 at 21:59
  • 1
    $\begingroup$ 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... $\endgroup$ – Benjamin Dickman Jun 18 '14 at 22:04
  • $\begingroup$ [FWIW: Down-voter is not me...] $\endgroup$ – Benjamin Dickman Jun 18 '14 at 23:24
  • $\begingroup$ @BenjaminDickman that's ok I couldn't care less about rep. $\endgroup$ – Bitwise Jun 19 '14 at 0:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.