<s>[INST] Combinatorial graph theory proof Why does $\binom{1/2}{n+1} * (-1)^n * 2^{2*n+1}$ equal $1/(n+1) * \binom{2n}{n}$?  I came across this in an exercise in Graph Theory and Its Applications by Gross and Yellen.  I haven't been able to solve it, can anyone give any insight?
 [/INST] We know that,
$$\binom{x}k=\frac{x^{\underline k}}{k!}$$
where $x^{\underline k}$ is the falling factorial function defined as $x^{\underline k}=x(x-1)(x-2)\cdots (x-k+1)$
Also, $x!!$ is the double factorial function defined as,
$$x!!=\begin{cases}x(x-2)(x-4)\cdots 4\cdot 2\cdot 1~,~\textrm{when }x\textrm{ is even}\\x(x-2)(x-4)\cdots 5\cdot 3\cdot 1~,~\textrm{when }x\textrm{ is odd}\end{cases}$$
Now,
$$\binom{1/2}{n+1}=\frac{\frac{1}{2}\cdot \left(-\frac{1}{2}\right)\cdot \left(-\frac{3}{2}\right)\cdots \left(-\frac{2n-1}{2}\right)}{(n+1)!}=\frac{(-1)^n\cdot (2n-1)!!}{2^{n+1}\cdot (n+1)!}\\ \implies \binom{1/2}{n+1}\cdot (-1)^n=\frac{(1)^n\cdot (2n-1)!!}{2^{n+1}\cdot (n+1)!}=\frac{(2n-1)!!}{2^{n+1}\cdot (n+1)!}\\ \implies \binom{1/2}{n+1}\cdot (-1)^n\cdot 2^{2n+1}=\frac{2^n(2n-1)!!}{(n+1)!}$$
Now, multiply numerator and denominator of RHS with $n!$ to get,
$$\binom{1/2}{n+1}\cdot (-1)^n\cdot 2^{2n+1}=\frac{\{2^n\cdot n!\}\cdot (2n-1)!!}{(n+1)\cdot (n!)^2}=\frac{(2n-1)!!\cdot (2n)!!}{(n+1)\cdot (n!)^2}=\frac{(2n)!}{(n+1)\cdot (n!)^2}$$
Since $\dbinom{2n}{n}=\dfrac{(2n)!}{n!\cdot n!}=\dfrac{(2n)!}{(n!)^2}$, we can write that,
$$\binom{1/2}{n+1}\cdot (-1)^n\cdot 2^{2n+1}=\frac{(2n)!}{(n+1)\cdot (n!)^2}=\frac{1}{n+1}\cdot \binom{2n}{n}\\ \implies \boxed{\dbinom{1/2}{n+1}\cdot (-1)^n\cdot 2^{2n+1}=\dfrac{1}{n+1}\cdot \dbinom{2n}{n}}$$
</s>