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.
 A: 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}
A: Unfinished approach that is too long for a comment:
I tried to use Sister Celine's method but there are annoying details:
Let $$F(n,k)=\frac{(-1)^{k-1} 16^k (k-1)! k! (k+n-1)!}{((2 k)!)^2 (n-k)!}.$$
Then whenever $F(n,k)\neq0$, $$F(n+1,k)/F(n,k)=\frac{k+n}{1-k+n}$$ and $$F(n,k+1)/F(n,k)=-\frac{4 k (n-k) (k+n)}{(k+1) (2 k+1)^2},$$ so by Sister Celine's method we find that $F$ satisfies the recursion
\begin{equation}
 \sum_{r=0}^3\sum_{s=0}^1 a_{r,s}(n) F(n-r,k-s)=0
\end{equation}
where the $a_{r,s}(n)$ equal
$$\left(
\begin{array}{cc}
 (1-2 n)^2 (n-2) n & 0 \\
 -(n-1) (2 n-1) (n (6 n-17)+9) & 8 (n-2) (n-1)^2 (2 n-1) \\
 (n-2) (2 n-1) (n (6 n-19)+12) & -8 (n-2)^2 (n-1) (2 n-1) \\
 -(n-3) (n-1) (2 n-5) (2 n-1) & 0 \\
\end{array}
\right)$$
whenever all $F(n-r,k-s)$ are defined. Now we would like to use this in order to deduce a recurrence for the sum $$G(n)=\sum_{k=1}^n F(n,k),$$ however we get issues since $F(n,0)$ is not well-defined. So maybe studying $\sum_{k=2}^n F(n,k)$ works better. 
In fact, we (mysteriously) get the following recurrence that I don't have the time to figure out a proof for:
$$\left(-2 n^3+13 n^2-26 n+15\right) G(n-3)+\left(-2 n^3+9 n^2-14 n+8\right) G(n-2)+\left(2 n^3-9 n^2+14
   n-7\right) G(n-1)+\left(2 n^3-5 n^2+2 n\right) G(n)=16 n-24.$$
Now we would have to prove that the right-hand side also satisfies this recurrence and we would be done.
