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.
Best Answer
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} $$