How many r-tuples are there such that sum of absolute values of entries is less than or equal to $n$?
That is, what is the cardinality of the set $ \{(x_1,...,x_r): x_i \in Z \text{ and }\mid x_1\mid+ ... + \mid x_r \mid \leq n\}$?
This should give me the growth function of the group $Z^r$ under the generating set $S=\{e_1,...,e_r\}$ where $ e_i=\{0, ...,0, 1,0,...,0\}$ with $1$ in the $i$-th position. It's known that the answer to this question is: $\sum_{k=0}^{r}2^k {r \choose k}{n \choose k}$. I'm trying to figure it out for myself.
Attempt: I have been able to figure out that the cardinality of $ \{(x_1,...,x_r): x_i \in Z^+ \text{ and }x_1+ ... + x_r \leq n\}$ is $n \choose k$.
Also I calculated cardinality of $ \{(x_1,...,x_k): x_i \in Z^+ \text{ and } x_1+ ... + x_k = n\}$ to be $n-1 \choose k-1$ via the stars and bars method.
However, I am a little stuck on combining these results (or otherwise) to figure out the question with the absolute values.