6
$\begingroup$

While verifying my answer to another question, I came across a problem of binomial coefficients:
Does $\hspace{.2cm}\displaystyle \prod_{k=1}^{n-1}\binom{n-1}{k}=\prod_{k=1}^{n-1}k^{2k-n}$ for all $n\in\mathbb{N}^+?$

I offer a proof by induction below, but I would appreciate references or alternative approaches.

$\endgroup$
1
  • $\begingroup$ If someone can think of a better title, please edit! $\endgroup$ Oct 8, 2014 at 20:44

2 Answers 2

4
$\begingroup$

Well, in each term of your product, the numerator is $(n-1)!$. Thus, the "total" numerator is $$\left((n-1)!\right)^{n-1}=\prod_{1}^{n-1}k^{n-1}$$

As for the denominator, each individual denominator is a product of 2 factorials, the argument of first factorial "grows" from $0$ to $(n-1)$, the argument of the second one "grows smaller" from $n-1$ to $0$. Thus, each argument appears exactly two times, and we have $\left(\prod_1^{n-1}k!\right)^2$. Note that in $\left(\prod_1^{n-1}k!\right)$ we come across number $k$ $n-k$ times, thus our denominator is $$\left(\prod_1^{n-1}k!\right)^2 = \prod_1^{n-1}k^{2(n-k)}$$

Trivial division allows to conclude. I favour this kind of proofs because you make virtually no formula manipulation, almost impossible to get it wrong.

$\endgroup$
1
  • $\begingroup$ That's a nice argument. Presumably one could distill it down to a one-line proof via adroit use of $\prod$ notation, but the intention of the proof via the verbal argument is evident. $\endgroup$ Oct 8, 2014 at 21:39
2
$\begingroup$

The identity can be proved by induction on $n$. For $n=1$, each side is an empty product and so both equal $1$, so we assume it is true for some $n\geq 1$. Then for $n+1$ we have

$$\prod_{k=1}^{n}\binom{n}{k}=\prod_{k=1}^{n-1}\binom{n}{k}=\prod_{k=1}^{n-1}\frac{n}{n-k}\binom{n-1}{k}=\frac{n^{n-1}}{(n-1)!}\prod_{k=1}^{n-1}\binom{n-1}{k},\\ \prod_{k=1}^{n}k^{2k-n-1}=n^{n-1}\prod_{k=1}^{n-1}k^{2k-n-1}=\frac{n^{n-1}}{\prod_{k=1}^{n-1}k}\left(\prod_{k=1}^{n-1}k^{2k-n}\right)=\frac{n^{n-1}}{(n-1)!}\prod_{k=1}^{n-1}k^{2k-n}.$$

Then the inductive hypothesis implies that these expressions are equal, and we conclude that the identity is true for all $n\in \mathbb{N}^+$.

$\endgroup$
2
  • $\begingroup$ Semiclassical, nice proof! +1. $\endgroup$ Oct 8, 2014 at 20:41
  • $\begingroup$ @OlivierOloa: Thanks! Proving it has the side benefit of confirming that my answer to the linked question agrees with the other long answer, so I was pleased to find a simple inductive proof. (Though I do hope someone can give a nice combinatorial argument...) $\endgroup$ Oct 8, 2014 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .