Is there a formula for $\sum^{n}_{k=1}\binom{ n-k }{h }k$?

Question

I'm trying to show $$\sum ^{400}_{m=1}\binom{ 400-m }{ 3 }m \sim 8.5 \times 10^9\,,$$ but can't seem to find a binomial coefficient identiy.

Answer 1

Hint: Apply the Hockey Stick lemma twice.

$$\sum ^{400}_{m=1} \left[ { 400 -m \choose 3 } \sum_{i=1}^{m} 1 \right] = \sum_{i=1}^{400} \left[\sum_{m=i}^{400}{ 400-m \choose 3 } \right] = \sum_{i=1}^{400} { i \choose 4 } = { 401 \choose 5 }$$

---

Note: There might be indexing errors as it's late and I'm going to sleep, but you should be able to get the gist.

Yes, this generalizes and can be expressed as an identity.

Answer 2

Let $a_k = \binom{k}a$ and $b_k=k$. What you want is $c_n=\sum_{k=0}^n a_kb_{n-k}$. There is a standard way to find this. We have that

$$A(x) = \sum_{k\geqslant a} \binom{k}a x^{k}=x^a\sum_{k\geqslant 0} \binom{k+a}a x^{k}= \frac{x^a}{(1-x)^{a+1}}$$

$$B(x) = \sum_{k\geqslant 0} k x^{k}=\frac x{(1-x)^2} $$

hence

$$C(x) = A(x)B(x) = \frac{x^{a+1}}{(1-x)^{a+3}}=x^{-1}\frac{x^{a+2}}{(1-x)^{a+3}}$$

so the general coefficient of $C$ is...?