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

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!

• The proof basically amounts to factoring out $2$ from every even number in the original product, thus leaving you with a product of odd numbers. Every other term in the product will ultimately be even. It feels like it might be easier to demonstrate in cases specifying where $n$ is even in one case, and inducting on the even integers, and then inducting on odd $n$ in another case, since it might make the math a little cleaner and the logic/wording in the proof less cumbersome, but that's just a guess. – Eevee Trainer Nov 4 '18 at 17:18
• Welcome to math.SE. Please see How to Ask a Good Question for information about what we look for on this site. In particular, you should try to the extent possible to include the source and motivation of each problem, not just a statement of a problem that you are trying to solve. – Carl Mummert Nov 4 '18 at 19:20

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)$$.

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. 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.

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