<s>[INST] Bound on sum of combinations I came across the following inequality $\sum_{i=0}^D \binom N i \le N^D+1$.
I am not sure how to prove this. I tried to do it by induction on $D$, and started with observing the values of sum for different values of $N$, and $D$. The values are as follows:
$$
        \begin{matrix}
        N \downarrow D \rightarrow  &0 &1& 2 &3 &4 &5& 6\\
        1 &1 &2& 2& 2& 2& 2& 2\\
2& 1& 3& 4& 4& 4& 4& 4\\
3 &1 &4 &7 &8 &8 &8 &8\\
4 &1 &5 &11 &15 &16 &16 &16\\
5 &1 &6 &16 &26 &31 &32 &32\\
        \end{matrix}
$$
Though form the base cases of $N=1, D=0$, and $N=1, D=2$, and so on, the inequality holds, but I am not sure how to proceed further. Any pointer on this would be great.
 [/INST] We shall prove the statement
$$\sum \limits _{i=0} ^D \binom N i \le N^D + 1, \ \forall N \ge 1, \forall \ 0 \le D \le N$$
using induction on $N$.
For $N = 1$, if $D = 0$ then $\binom 1 0 = 1 \le 1 ^0 + 1$, and if $D = 1$ then $\binom 0 0 + \binom 1 0 = 1 + 1 = 2 \le 1^1 + 1$. Thus, for $N = 1$ the statement is verified.
Let us assume it true for $N$ and let us prove it for $N + 1$.
If $D = N + 1$, then it is clear that
$$\sum \limits _{i = 0} ^D \binom {N + 1} i = \sum \limits _{i = 0} ^{N + 1} \binom {N + 1} i 1^i 1^{N + 1 - i} = (1 + 1) ^{N + 1} = 2^{N + 1} \le (N+1) ^{N+1} + 1 .$$
If $D=0$, the conclusion is trivial: $\binom {N+1} 0 = 1 \le (N+1)^0 + 1$.
For $1 \le D \le N$, using Pascal's formula $\binom {N + 1} i = \binom N i + \binom N {i-1}$ we have that
$$\sum \limits _{i = 0} ^D \binom {N + 1} i = 1 + \sum \limits _{i = 1} ^D \binom {N + 1} i = 1 + \sum \limits _{i = 1} ^D \left( \binom N i + \binom N {i-1}\right) = \\ 1 + \sum \limits _{i = 1} ^D \binom N i + \sum \limits _{i = 1} \binom N {i-1} = \sum \limits _{i = 0} ^D \binom N i + \sum \limits _{j = 0} ^{D-1} \binom N j \le N^D + 1 + N^{D-1} + 1 \le \\ N^D + D N^{D-1} + 1 + 1 \le (N+1) ^D + 1$$
as desired (we have used that $(N+1)^D = N^D + D N^{D-1} + \dots + 1$).
</s>