# $\sum_{k=1}^n \frac 1 k \sum_{j=1}^k a_j \binom k j = \sum_{k=1}^n \frac {a_k}k \binom n k$

I am trying to prove

$\sum_{k=1}^n \frac 1 k \sum_{j=1}^k a_j \binom k j = \sum_{k=1}^n \frac {a_k}k \binom n k$

and hoping to avoid proof by induction.

The textbook this comes from doesn't specify what $$a_k$$ is, but probably the proof should allow it to be complex numbers or, in the most restrictive case, any sequence of positive integers.

However, because of the inclusion of this arbitrary sequence, I'm not sure how I could prove this identity without induction -- a combinatorial argument seems to be made impossible. I'm not certain of that but it's hard to imagine how an arbitrary $$a_k$$ could be accounted for in a combinatorial argument.

• It's easier to see it if you write the right side with $j$ as the variable instead of $k.$ Then use: $$\sum_{k=1}^{n}\sum_{j=1}^k f(j,k)=\sum_{j=1}^n\sum_{k=j}^n f(j,k)$$ Commented Sep 17, 2022 at 2:40

Interchange the order of summation to find that $$\sum_{k=1}^n \frac 1 k \sum_{j=1}^k a_j \binom k j =\sum_{j=1}^na_{j}\sum_{k=j}^n\frac{1}{k}\binom{k}{j}=\sum_{j=1}^n\frac{a_{j}}{j}\sum_{k=j}^n\binom{k-1}{j-1}$$ But note that $$\sum_{k=j}^n\binom{k-1}{j-1} = \sum_{k=j-1}^{n-1}\binom{k}{j-1} =\binom{n}{j}$$ by the Hockey stick identity.