Can I cancel out factorials in proofs?

Question

I encountered the following question in a discrete math course:

Prove that $ \binom{2n}{k-1} < \binom{2n}{k} $ for $k = 1, 2, \ldots , n$.

Hint: This should be a very cleanly written proof.

I'm working through this proof and I'm at a step where I have similar numerators but with a factorial.

My question is: Can I "cancel out" factorials?

Well, factorials are simply product of integers, and if you have the same set of integers in numerator and denominator, you can cancel them, so... — rogerl, Mar 27 '15 at 00:26
Do you need a proof for that combinatorial identity? If so, then I can write one. — Prasun Biswas, Mar 27 '15 at 00:30

score 4 · Answer 1 · answered Mar 27 '15 at 00:29

You can cancel, but you have to be careful how you do it. For example: $\frac{k!}{(k+1)!}$ can be reduced to $\frac{1}{k+1}$ by cancelling the factorial portion on top, but you CANNOT cancel like: $\frac{k!}{(k+1)!}=\frac{k}{k+1}$ effectively cancelling the "!" symbol.

Think about what the factorial means and it will be clear what you can do.

$$\frac{k!}{(k+1)!}=\frac{k(k-1)(k-2)...(3)(2)(1)}{(k+1)(k)(k-1)(k-2)...(3)(2)(1)}=\frac{1}{k+1}.$$

Other factorials are similar. Handy things to keep in mind are facts like $(n+1)!=(n+1)\cdot n!$, etc.

Or, from the definition of factorial, $(k+1)! = k!(k+1)$, which makes the cancellation "obvious". — marty cohen, Mar 27 '15 at 02:15

score 2 · Accepted Answer · answered Mar 27 '15 at 00:35

2

Hint: After you cancel out factorials, you will find out that $$ \frac{\binom{2n}{k}}{\binom{2n}{k-1}} = \frac{2n-k+1}{k} > 1. $$

answered Mar 27 '15 at 00:35

Yuval Filmus

57,157

1

Damn! I was gonna post this one. :( – Prasun Biswas Mar 27 '15 at 00:36
As my good deed for today, I'll upvote you. – marty cohen Mar 27 '15 at 02:14

Can I cancel out factorials in proofs?

2 Answers2