<s>[INST] Proving $\sum _{k=1}^n \frac{(-1)^{k-1} 16^k (k-1)! k! (k+n-1)!}{((2 k)!)^2 (n-k)!}=\frac{4}{n}\sum _{k=1}^n \frac{1}{2 k-1}$ How can one prove
$$
\sum_{k = 1}^{n}\frac{\left(-1\right)^{k - 1}\, 16^{k}\,
\left(k - 1\right)!\, k!\, \left(k + n - 1\right)!}
{\left[\left(2k\right)!\right]^{\, 2}\,\left(n - k\right)!} =
\frac{4}{n}\sum_{k = 1}^{n}\frac{1}{2k - 1}
$$
I was given this without proof, but only a hint (to evaluate $\int_{0}^{\pi/2}\frac{2}{n}\,\frac{1 - \cos\left(2nx\right)}{\sin\left(x\right)} \, dx$ in $2$ ways) instead. By induction the integral is easily seen equivalent to RHS, but I wonder how on earth it's related to LHS. Any help will be appreciated.
 [/INST] Remarking that
\begin{equation}
\sum_{k=1}^n\sin\left( \left( 2k-1 \right)x \right)=\frac{\sin^2nx}{\sin x}
\end{equation} 
the proposed integral
\begin{align}
I_n&=  \frac{2}{n}\int_0^{\frac{\pi }{2}}\frac{1-\cos (2 n x)}{\sin (x)} \, dx\\
 &= \frac{4}{n}\int_0^{\frac{\pi }{2}}\frac{\sin^2nx}{\sin x},dx\\
 &=\frac{4}{n}\sum_{k=1}^n\int_0^{\frac{\pi }{2}}\sin\left( \left( 2k-1 \right)x \right)\,dx\\
 &=\frac{4}{n}\sum_{k=1}^n\frac{1}{2k-1}\\
 &=\text{rhs}
\end{align}
which shows that the integral is equal to the rhs of the identity.
This decomposition suggests the use of the Chebyshev polynomials to evaluate the lhs,
\begin{equation}
\text{lhs}=\sum _{k=1}^n \frac{(-1)^{k-1} 16^k (k-1)! k! (k+n-1)!}{((2 k)!)^2 (n-k)!}
\end{equation} 
Indeed, the Chebyshev polynomials of the first kind reads
\begin{equation}
T_n(z)=n\sum_{k=0}^n(-2)^k\frac{(k+n-1)!}{(n-k)!(2k)!}(1-z)^k
\end{equation} 
and thus
\begin{equation}
\sum_{k=1}^n(-1)^{k-1}\frac{(n+k-1)!}{(n-k)!(2k)!}\left( 2(1-z) \right)^k=\frac{1}{n}\left( 1-T_n(z) \right)
\end{equation} 
and with $Z=2(1-z)$,
\begin{equation}
\sum_{k=1}^n(-1)^{k-1}\frac{(n+k-1)!}{(n-k)!(2k)!}Z ^k=\frac{1}{n}\left[ 1-T_n(1-\frac{Z}{2}) \right]
\end{equation} 
This summation is very similar to the proposed one. To introduce the missing factor $\frac{(k-1)!k!}{(2k)!}=\mathrm{B}(k,k+1)$ (here, $\mathrm{B}(k,k+1)$ is the Beta function), we use the integral representation:
\begin{equation}
\int_{0}^{\pi/2}{\sin^{2a-1}}\theta{\cos^{2b-1}}\theta\mathrm{d}\theta=\tfrac{1}{2}\mathrm{B}\left(a,b\right)
\end{equation} 
with $a=k,b=k+1$, to express
\begin{align}
\mathrm{B}(k,k+1)&=2\int_{0}^{\pi/2}{\sin^{2k-1}}\theta{\cos^{2k+1}}\theta\,d\theta\\
&=2^{1-2k}\int_{0}^{\pi/2}\frac{\cos\theta}{\sin\theta}\sin^{2k}2\theta\,d\theta
\end{align} 
Thus
\begin{align}
\text{lhs}&=\sum _{k=1}^n \frac{(-1)^{k-1} 16^k  (k+n-1)!}{(2 k)! (n-k)!}\mathrm{B}(k,k+1)\\
&=2\int_{0}^{\pi/2}\frac{\cos\theta}{\sin\theta}\,d\theta\sum _{k=1}^n \frac{(-1)^{k-1} (k+n-1)!}{(2 k)! (n-k)!}16^k2^{-2k}\sin^{2k}2\theta\\
&=\frac{2}{n}\int_{0}^{\pi/2}\frac{\cos\theta}{\sin\theta}
\left[ 1-T_n(1-2\sin^22\theta) \right]\,d\theta\\
&=\frac{2}{n}\int_{0}^{\pi/2}\frac{\cos\theta}{\sin\theta}
\left[ 1-T_n(\cos4\theta) \right]\,d\theta
\end{align}
But $T_n(\cos4\theta)=\cos 4n\theta$ and $1-\cos 4n\theta=2\sin^22n\theta$. We obtained then
\begin{equation}                                                                                       \text{lhs}=\frac{4}{n}\int_{0}^{\pi/2}\frac{\cos\theta}{\sin\theta}\sin^22n\theta\,d\theta\                                                                        \end{equation} 
By changing $\theta=u/2$ in the above integral and using simple trigonometric manipulations,
\begin{align}
\text{lhs}&=\frac{2}{n}\int_{0}^{\pi}\frac{\cos\frac{u}{2}}{\sin\frac{u}{2}}\sin^2nu\,du\\
&=\frac{4}{n}\int_{0}^{\pi}\frac{\cos^2\frac{u}{2}}{\sin u}\sin^2nu\,du\\
&=\frac{2}{n}\int_{0}^{\pi}\frac{\sin^2nu}{\sin u}\left( 1+ \cos u\right)\,du\\
&=\frac{2}{n}\int_{0}^{\pi}\frac{\sin^2nu}{\sin u}\,du+\frac{2}{n}\int_{0}^{\pi}\frac{\sin^2nu}{\sin u} \cos u\,du
\end{align}
By symmetry, the second integral vanishes and using symmetry for the first one,
\begin{align}
\text{lhs}&=\frac{4}{n}\int_{0}^{\pi/2}\frac{\sin^2nu}{\sin u}\,du\\
&=I_n
\end{align}
</s>