Sum of non-negative integers less than a given integer?

Question

Let $N \in \mathbb{Z}_{\geq 0}$ and let $\alpha = (a_1,...,a_n) \in \mathbb{Z}_{\geq 0}^{n}$.

I am interested in the cardinality of the set ${\{\alpha \in \mathbb{Z}_{\geq 0}^{n} : |\alpha| \leq N}\}$, where $|\alpha| = a_1 + a_2 + ... + a_n$.

Does anyone know how to prove this? I assume there is some sort of combinatorial argument but I'm stuck? Any hints would be appreciated.

Answer 1

Let $A(n, N)$ be your number. Define $A_r(n, N)$ to be the cardinality of the set $$ \{\alpha\in \Bbb Z_{\geq 0}^n\mid |\alpha|\leq N, a_n = r\} $$ Clearly, we have $$ A(n, N) = \sum_{r = 0}^N A_r(n, N) $$ Also, note that by simply removing the last element of $\alpha$, we have $$ A_r(n, r) = A(n-1, N-r) $$ which is to say $$ A(n, N) = \sum_{r = 0}^N A(n-1, N-r) $$ Comparing the sum for $A(n, N)$ and the sum for $A(n, N-1)$, we get $$ A(n, N) = A(n-1, N) + A(n, N-1) $$ and we see that these are just relabelled binomial cefficients: $$ A(n, N) = \binom{n+N}{N} $$

Answer 2

Hint: for $\alpha = N$ you are looking for weak compositions of $N$ into $n$ parts. You can solve that with the usual stars and bars argument. Now just sum the number of compositions of $k$ from $0$ to $N$

Answer 3

Think of this as putting $N$ items into $n+1$ bins, where $a_1,\dots,a_n$ are the contents of the first $n$ bins. Using stars and bars, this gives $\binom{N+n}{n}$.