Show that $\prod_{k=1}^n (n+k) = 2^n \prod_{k=1}^n (2k-1)$ for all $n\in Z^+$

Question

Show that $$\prod_{k=1}^n (n+k) = 2^n \prod_{k=1}^n (2k-1)$$ for all $n\in Z^+$.

I think I'm supposed to use induction to prove this, but I can't seem to figure out how. Any help would be appreciated, thanks in advance!

Answer 1

Hint: Induction \begin{eqnarray*} (n+1) \prod_{k=1}^{n+1}(n+1+k)=\left(\prod_{k=1}^{n}(n+k) \right) (2n+1)(2n+2) = \cdots \end{eqnarray*}

Answer 2

Maybe you can prove by induction that $$\prod_{k=1}^n(n+k)=\frac{(2n)!}{n!}.$$ Then, prove that $$\frac{(2n)!}{n!}=\prod_{j=1}^n\frac{2j}{j}\ \prod_{k=1}^n\,(2k-1).$$

---

There is a combinatorial proof for the whole thing though. Let's say you want to create $n$ pairs from a group of $2n$ people, say with names (or labels) in the set $\{1,2,\ldots,2n\}$. In each pair, one person is the leader, and the other is the follower. The order of the groups does not matter.

We may do the job as follows. First, select the leaders. The first leader can be chosen in $2n=n+n$ ways, the second leader can be chosen in $2n-1=n+(n-1)$ ways, so on and so forth. So, there are $\prod_{k=1}^n(n+k)$ ways to pick the $n$ leaders. Now, let $t_1,t_2,\ldots,t_n$ be the remaining people, with $t_1<t_2<\ldots<t_n$. Since we do not distinguish the order of the groups, the pairing of $t_j$ with the $j$th leader creates a unique grouping. Therefore, the work can be done in exactly $\prod_{k=1}^n(n+k)$ ways.

On the other hand, we may pick people as follows. First, the person named $a_1=2n$ has to be paired with somebody. There are $2n-1$ ways to choose this person's partner, and $2$ ways to decide who the leader is going to be. Then, we let $a_2$ be the guy with largest label who has not been paired. There are $2n-3$ ways to pick $a_2$'s partner, and $2$ ways to decide who's boss. We continue to do so, and at the end, the work can be done in $\prod_{k=1}^n2(2n+1-2k)=2^n\prod_{k=1}^n(2k-1)$ ways.

Answer 3

Induction is not necessarily needed.

We obtain for $n\in Z^+$ \begin{align*} \color{blue}{2^n \prod_{k=1}^n (2k-1)}&=2^n(2n-1)!!\tag{1}\\ &=2^n\frac{(2n)!}{(2n)!!}\tag{2}\\ &=2^n\frac{(2n)!}{2^nn!}\tag{3}\\ &=\frac{(2n)!}{n!}\tag{4}\\ &\,\,\color{blue}{=\prod_{k=1}^n(n+k)} \end{align*} and the claim follows.

Comment:

• In (1) we use double factorials $(2n-1)!!=(2n-1)(2n-3)\cdots3\cdots 1$.

• In (2) we use the identity $(2n)!=(2n)!!(2n-1)!!$.

• In (3) we use the identity $(2n)!!=(2n)(2n-2)\cdots 4\cdot 2=2^n n!$.

• In (4) we have $\frac{(2n)!}{n!}=(2n)(2n-1)\cdots(n+1)$.