Evaluate
$$a_n = {\large\sum_{k=1}^n} \sum_{i=1}^k i{k \choose i}{{n – k – 1} \choose
k – i – 1}$$
I derived this sum when working on the following problem
Find the total number of $1$'s in the compositions of $n \ge 2$.
WolframAlpha states that $a_n = 2^{n – 3}(n + 2)$ but I'm unable to come up with a proof of this claim. I've been trying to think of this combinatorially; for example, as the number of subsets in a set of $n-3$ elements where there are $n + 2$ sets to choose from. However, I haven’t been able to relate this to the sum above.
Comments:
- Please view this as if you did not know that the sum evaluates to $2^{n-3}(n + 2).$ That is to say, inductive proofs aren’t viable unless they can be reasonably conjectured.
- Please do not provide alternate solutions to the problem of finding the number of $1$'s in the compositions of $n$. I am specifically looking for a method to evaluate the sum.
Side Query:
Strangely when I input values for $n$ into the summation, WolframAlpha gives me a value that is $n$ higher than the evaluated expression. If you are aware of why this is the case, please feel free to comment.
Best Answer
For $n\geq k\geq 2$, by Vandermonde's identity, $$\sum_{i=1}^{k-1} i{k \choose i}{{n - k - 1} \choose k - i - 1}=k\sum_{i=1}^{k-1} {k-1 \choose i-1}{{n - k - 1} \choose k - i - 1}=k\binom{n-2}{n-k}.$$ Therefore $$\begin{align}\sum_{k=2}^{n} \sum_{i=1}^{k-1} i{k \choose i}{{n - k - 1} \choose k - i - 1}&=\sum_{k=2}^{n}k\binom{n-2}{n-k}=\sum_{k=0}^{n-2}(n-k)\binom{n-2}{k} \\&=n\sum_{k=0}^{n-2}\binom{n-2}{k}-(n-2)\sum_{k=1}^{n-2}\binom{n-3}{k-1}\\ &=n2^{n-2}-(n-2)2^{n-3}=(n+2)2^{n-3}. \end{align}$$ which is the same formula given at OEIS A045623.