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.


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.

  • 2
    $\begingroup$ Can you see how to maximize the right hand side? $\endgroup$ – TokenToucan Dec 29 '15 at 18:26
  • $\begingroup$ Thanks. When $\alpha_k = n+k$ and $\alpha_i=n$. Alas, that I know because of calculations, not by way of logic. $\endgroup$ – Abu Bakar Dec 29 '15 at 18:29
  • 3
    $\begingroup$ (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 $\endgroup$ – TokenToucan Dec 29 '15 at 18:42
  • 1
    $\begingroup$ Post as an answer! @CuddlyCuttlefish $\endgroup$ – mysatellite Dec 29 '15 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.