# Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity:

$$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For

$\alpha_i<\alpha_j$ for $i<j$

$0\leq \alpha_i \leq n+k$

Also $\binom{a}{i}=0$ for $a<i$

Similar to the hockey-stick theorem. Not sure how to apply mathematical induction here.

Edit:

The right hand side of the inequality gets maximum value for $\alpha_1=n+1$ and $\alpha_k=n+k$. Therefore

$$\binom{n+k+1}{k} > \sum_{i=1}^k \binom{n+i}{i}$$ comparing with hockey-stick theorem \begin{eqnarray} \binom{n+k+1}{k} &=& \sum_{i=0}^k \binom{n+i}{i} \\ &=&\sum_{i=1}^k \binom{n+i}{i} + 1 \\ &>& \sum_{i=1}^k \binom{n+i}{i}\\ &>& \sum_{i=1}^k \binom{\alpha_i}{i} \end{eqnarray} Q.E.D

Thanks to CuddlyCuttlefish for suggesting maximization of R.H.S of inequality.

• Can you see how to maximize the right hand side? – TokenToucan Dec 29 '15 at 18:26
• Thanks. When $\alpha_k = n+k$ and $\alpha_i=n$. Alas, that I know because of calculations, not by way of logic. – Abu Bakar Dec 29 '15 at 18:29
• (I think you mean $\alpha_i = n+i$, but that's exactly right) You can actually use the hockey stick theorem to solve this problem, using that fact – TokenToucan Dec 29 '15 at 18:42
• Post as an answer! @CuddlyCuttlefish – mysatellite Dec 29 '15 at 18:51