Show $\frac{(3n+1)! n!}{(2n+1)!}$ can be written as a sum of ratios of factorials

Question

I am trying to show that for all $n$ that $$ \frac{n!(3n+1)!}{(2n+1)!} = \sum_{k=0}^n \frac{(n+k)!(2n-k)!}{k!(n-k)!} $$

I have tried proving this by induction, but I could not get it to work due to the right hand side being hard to reduce to the inductive hypothesis and am truly quite stuck.

I would greatly appreciate any hints at a solution.

Answer 1

$\frac{n!(3n+1)!}{(2n+1)}!=n!^2 {3n+1 \choose 2n+1}$

$\frac{(n+k)!(2n-k)!}{k!(n-k)!}=n!^2{n+k \choose n}{2n-k \choose n}$

$x^k in (1-x)^{-(n+1)} is {n+k \choose n}$

$x^{n-k} in (1-x)^{-(n+1)} is {2n-k \choose n}$

so our summation we want to find out(as pointed above by @John) is $x^n\ in\ (1-x)^{-(2n+2)}$ which is ${3n+1 \choose n}$

Answer 2

Here is a combinatorial argument. There are $\binom{3n + 1}{2n+1}$ ways to choose $2n + 1$ items from among $3n + 1$ items. Here is one way to count them. First, put the $3n + 1$ items into some sort of order. Next, among each of the combinations of $2n + 1$ items, consider the position of the $n + 1$'st item, i.e., so there are $n$ items before it and $n$ items after it. There must be at least $n$ positions available both before & after this item, so the smallest position is $n + 1 = (n + 1) + 0$ and the largest is $(3n + 1) - n = 2n + 1 = (n + 1) + n$. This means the valid range for this $n + 1$'st item can be expressed as being from $n + 1 + k$ for $k$ from $0$ to $n$.

The number of ways to choose the $n$ items before the $n + 1$'st item would be $\binom{n+k}{n}$, and there are $\binom{3n + 1 - (n + 1 + k)}{n} = \binom{2n-k}{n}$ ways to choose the $n$ items after it. To get the number of combinations for each $k$, you would need to multiply the number of combinations of these $2$ independent groups. For the total of the combinations, you will then add these products for $k$ from $0$ to $n$. In other words, you get by writing out the factorials and multiplying both sides by $(n!)^2$ that

$$\begin{equation}\begin{aligned} \binom{3n + 1}{2n+1} & = \sum_{k=0}^{n}\binom{n+k}{n}\binom{2n-k}{n} \\ \frac{(3n+1)!}{n!(2n+1)!} & = \sum_{k=0}^n \frac{(n+k)!(2n-k)!}{(n!k!)(n!(n-k)!)} \\ \frac{n!(3n+1)!}{(2n+1)!} & = \sum_{k=0}^n \frac{(n+k)!(2n-k)!}{k!(n-k)!} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$