My friend showed me a difficult combinatorial identity I cannot solve.
Prove that: $$\sum_{k=2}^n \frac{(k-2){n-k+2\choose k-1}+k{n-k+1\choose k-1}}{k{n\choose k}}=1$$ for all $n\ge 2$.
How do I prove this?
Edit: I would like to bump this again, due to lack of attention.
I do not like this proof, for reasons that will become obvious.
By shifting the summation index and using a binomial ID in the denominator, we can write the LHS (left-hand side) of the proposed identity as $$D_n:=\sum_{k=1}^{n-1} \frac{ (k-1)\binom{n-k+1}{k} + (k+1)\binom{n-k}{k} }{n\binom{n-1}{k}} $$ For the denominator, use the ID (beta integral identity) $$\frac{1}{n\binom{n-1}{k}}=\int_0^1t^k(1-t)^{n-1-k} dt = 2\int_0^{\pi/2} \cos^{2k+1}(t) \ \sin^{2n-2k-1}(t) dt $$ This is done so that the sum can be solved in explicit form in terms of the Chebyshev polynomials of first and second kind. e.g., $$\sum_{k=0}^n (-1)^kx^{2k}\binom{n-k}{k} = U_n\big(\frac{1}{2x}\big)x^n$$ With one integration by parts and simplification, we can write an equivalent expression, with $\omega_n(t)=(n\cos^{2n-1}(t)-(n+1)\cos^{2n+1}(t))\sin{(t)},$
$$ (eq.1) \quad \frac{1}{2}D_n = \int_{0}^{\pi/2} \omega_n(t)(i\tan{t})^{n+1}U_{n+1}\big(\frac{1}{2i\ \tan{t}} \big) dt \quad+ $$ $$+ \quad \int_{0}^{\pi/2} \omega_n(t)(i\tan{t})^{n}U_{n}\big(\frac{1}{2i\ \tan{t}} \big) dt -\frac{2}{n+1}\int_{0}^{\pi/2} \omega_n(t)(i\tan{t})^{n+1}T_{n+1}\big(\frac{1}{2i\ \tan{t}} \big) dt$$
At this point I tried to use recurrence formulas for the Chebyshev polynomials to prove $D_{n+1} = D_n,$ but I was unsuccessful. Therefore, I did the following: create a generating function by operating on both sides with $\sum_{n=1}^\infty x^n/n $. Now by explicit calculation, $D_1 = 0.$ Therefore we want to verify $$ (eq.2)\quad -(x+\log{(1-x)})/2 = \sum_{n=1}^\infty x^n/n \ RHS(*) $$ To do this, you need six explicit sums, which are not difficult to derive: $$\sum_{n=1}^\infty \frac{x^n}{n} U_{n}(y) = \frac{y}{\sqrt{1-y^2}} \text{arctan}\big(x\frac{\sqrt{1-y^2}}{1-xy}\big)-\frac{1}{2}\log{(1+x^2-2xy)} $$
$$\sum_{n=1}^\infty \frac{x^n}{n} U_{n+1}(y) = \frac{2y^2-1}{\sqrt{1-y^2}} \text{arctan}\big(x\frac{\sqrt{1-y^2}}{1-xy}\big)-y\log{(1+x^2-2xy)} $$
$$\sum_{n=1}^\infty x^n U_{n}(y) = \frac{1}{1-2xy+x^2}-1 $$
$$\sum_{n=1}^\infty x^n U_{n+1}(y) =\frac{1}{x}\Big( \frac{1}{1-2xy+x^2}-1 -2xy\Big)$$
$$\sum_{n=1}^\infty \frac{x^n}{n+1} T_{n+1}(y) = \frac{1}{x}\Big(-\frac{1}{2}\log{(1+x^2-2xy)} - xy\Big) $$
$$\sum_{n=1}^\infty \frac{x^n}{n} T_{n+1}(y) = -\sqrt{1-y^2} \text{arctan}\big(x\frac{\sqrt{1-y^2}}{1-xy}\big)-\frac{y}{2}\log{(1+x^2-2xy)} $$
With these closed forms, the indefinite integrals are solvable in closed form by Mathematica. There is considerable simplification needed to finally get the form on the LHS of (eq.2).
I detest this proof because it does not give a hint at all about how the identity was discovered, and the huge amounts of simplification that must be performed with a CAS and human intervention.
This can be turned into a telescoping sum.
Applying the Pascal's triangle recurrence to the first binomial coefficient in the numerator yields $$ \binom{n-k+2}{k-1}=\binom{n-k+1}{k-2}+\binom{n-k+1}{k-1}, $$ which allows us to rewrite the identity as $$ D_n=\sum_{k\ge2}\frac{(k-2)\binom{n-k+1}{k-2}+2(k-1)\binom{n-k+1}{k-1}}{k\binom{n}{k}}=1.\tag{1} $$ We have named the left side of the identity $D_n$ and observed that the upper limit can be taken to be $\infty$ since the summand becomes $0$ after $k\approx\frac{n}{2}$.
The sum now telescopes by combining the second term of the $k^\text{th}$ summand with the first term of the $(k+1)^\text{st}$ summand: \begin{align} D_n&=\frac{(2-2)\binom{n-2+1}{2-2}}{2\binom{n}{2}}+\sum_{k\ge2}\left[\frac{2(k-1)\binom{n-k+1}{k-1}}{k\binom{n}{k}}+\frac{(k-1)\binom{n-k}{k-1}}{(k+1)\binom{n}{k+1}}\right]\\ &=\sum_{k\ge2}\left[\frac{2(k-1)(n-k)\binom{n-k+1}{k-1}}{kn\binom{n-1}{k}}+\frac{(k-1)\binom{n-k}{k-1}}{n\binom{n-1}{k}}\right]\\ &=\sum_{k\ge2}\left[\frac{2(k-1)(n-k)\left[\binom{n-k}{k-2}+\binom{n-k}{k-1}\right]}{kn\binom{n-1}{k}}+\frac{(k-1)\binom{n-k}{k-1}}{n\binom{n-1}{k}}\right]\\ &=\sum_{k\ge2}\left[\frac{(k-2)n\binom{n-k}{k-2}+k(n-2k+2)\binom{n-k}{k-2}+2(k-1)(n-k)\binom{n-k}{k-1}}{kn\binom{n-1}{k}}+\frac{(k-1)\binom{n-k}{k-1}}{n\binom{n-1}{k}}\right]\\ &=\sum_{k\ge2}\frac{(k-2)n\binom{n-k}{k-2}+k(k-1)\binom{n-k}{k-1}+2n(k-1)\binom{n-k}{k-1}-2k(k-1)\binom{n-k}{k-1}+k(k-1)\binom{n-k}{k-1}}{kn\binom{n-1}{k}}\\ &=\sum_{k\ge2}\frac{(k-2)\binom{n-k}{k-2}+2(k-1)\binom{n-k}{k-1}}{k\binom{n-1}{k}}\\ &=D_{n-1}. \end{align} In the second line we have used $\binom{n}{r}=\frac{n}{n-r}\binom{n-1}{r}$ to rewrite the first denominator and $r\binom{n}{r}=n\binom{n-1}{r-1}$ to rewrite the second denominator. In the third line we have used the Pascal's triangle recurrence in the first numerator. Since $D_n=D_{n-1}$, the result follows by induction.
The denominator of the summand of $(1)$ is the number of selections of $k$ elements from $n$ with one marked element. Let's say that the $n$ elements are members of an organization ranked by seniority, with $1$ having highest seniority and $n$ having lowest, and that a committee of $k$ members is to be chosen with one member designated as chairperson. Then the numerator of the summand may be interpreted as the number of such committees in which the highest seniority member has rank $k-2$ or $k-1$ and in which the chairperson has seniority lower than either of those members. It might be interesting to try to understand the manipulations above in terms of this interpretation.
