CLRS: Asked to prove a result and then told to give a counter example I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix:


  
  Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$.
  
  
  $${n \choose j + k} \le {n \choose j} {n-j \choose k}$$
  
  Privde both an algebraic proof and an argument based on a method for
  choosing $j+ k$ items out of $n$. Give an example in which equality
  does not hold.


Here I am asked to prove it and then give a counter example. I can't seem to find any problem with the proof or the couter example, $n=4$, $j=k=1$. Puzzeled!

Here is a proof:


  First, let's establish that, $j!k!\le (j+k)!$. Both sides have the
  same number of terms, but the right side has $k$ terms more -
  $(j+1)(j+2)\ldots(j+k)$ - that are greeter than the corresponding
  terms on the left side $1\cdot2\cdot\ldots\cdot k$.
  
  Thus:
  
  $${n \choose j}{n-j \choose k}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{k!(n-j-k)!}=\frac{n!}{j!k!(n-j-k)!}\ge\frac{n!}{(j+k)!(n-j-k)!}={n \choose j+k}$$
You aren't asked to give a counterexample to the proof, as that would be impossible.

Instead, they're asking for an example where equality does not hold, that is, the left hand side is strictly smaller than the right hand side. That's not a counterexample since the theorem states less or equal.