Number of integral solutions to a linear inequality I am trying to show the following identity:
Let $k,n \in \mathbb{N}$. Then
$$
\text{card}\{x \in \mathbb{Z}^n: \sum_{i=1}^n |x_i| \leq k\} =\sum_{i=0}^n 2^{n-i} {n \choose i}{k \choose n-i}.
$$
My attempt: Let $A=\{x \in \mathbb{Z}^n: \sum_{i=1}^n |x_i| \leq k\}$. Let $0\leq i \leq n$. Let $x_1,\ldots,x_{n-i}\geq 1$ be such that $x_1+\ldots+x_{n-i} \leq k$. Then it is easy to see that $|A|=\sum_{i=0}^n 2^{n-i} {n \choose i} |\text{no. of positive integral solutions to } x_1+\ldots+x_{n-i} \leq k| $. 
However, I am getting the number of positive integral solutions to $x_1+\ldots+x_{n-i} \leq k$ as not equal to ${k \choose n-i}$. Can anyone help me?
 A: Hint 1: number of positive integral solutions to $x_1+\ldots+x_{n-i} \leq k$ equals the number of all non-negative integral solutions to $y_1+\ldots+y_{n-i} \leq k-(n-i)$.
Hint 2: for any integer $r\ge 1$
$${r-1 \choose r-1}+{r \choose r-1}+\cdots+{k-1 \choose r-1}={k \choose r}.$$
A: We get for the LHS that it is
$$[z^k] \frac{1}{1-z} \left(1+2z+2z^2+\cdots\right)^n
= [z^k] \frac{1}{1-z} \left(1+2\frac{z}{1-z}\right)^n
\\ = [z^k] \frac{(1+z)^n}{(1-z)^{n+1}}.$$
Extracting coefficients we obtain
$$\sum_{q=0}^k {n\choose q} {k-q+n\choose n}
= \sum_{q=0}^k {n\choose q} {k-q+n\choose k-q}.$$
Introduce the integral 
$${k-q+n\choose k-q}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{k-q+n}}{z^{k-q+1}} \; dz.$$
This enforces the range (pole vanishes when $q\gt k$) so we may extend
the sum to $n$, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{k+n}}{z^{k+1}} 
\sum_{q=0}^n {n\choose q} \frac{z^q}{(1+z)^q}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{k+n}}{z^{k+1}} 
\left(1+\frac{z}{1+z}\right)^n
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{k}}{z^{k+1}} 
(1+2z)^n
\; dz.$$
We  evaluate this  using  the  negative of  the  residue at  infinity
to find (the residues sum to zero)
$$\mathrm{Res}_{z=\infty}
\frac{(1+z)^{k}}{z^{k+1}} (1+2z)^n
= -\mathrm{Res}_{z=0} \frac{1}{z^2}
(1+1/z)^k z^{k+1} (1+2/z)^n
\\ = -\mathrm{Res}_{z=0} \frac{1}{z}
(1+z)^k  \frac{(2+z)^n}{z^n}
= -\mathrm{Res}_{z=0} \frac{1}{z^{n+1}}
(1+z)^k (2+z)^n.$$
Extracting the residue and flipping the sign we get
$$\sum_{q=0}^n {n\choose q} 2^{n-q} {k\choose n-q}.$$
This is the RHS as claimed.
Remark. This  also works when $k  \gt n$ because  when we lower
the upper  limit of the  sum to $n$  we are omitting terms  that would
have been zero anyway due to the ${n\choose q}$ term.
A: Let $t=k-\left(|x_1|+\cdots+|x_n|\right)$, 
so we want to find the number of solutions of $|x_1|+\cdots+|x_n|+t=k$
where the $x_i$ and $t$ are integers and $t\ge0$.
For each $i$ with $0\le i\le n$, we can
1) choose $i$ of the terms $x_1,\cdots,x_n$ to be 0 in $\binom{n}{i}$ ways 
2) choose the signs of the remaining $n-i$ terms in $2^{n-i}$ ways
3) If we let $y_1,\cdots,y_{n-i}$ be the terms of the form $|x_j|$ chosen to be nonzero, 
$\hspace{.2 in}$we must find the number of solutions of $y_1+\cdots+y_{n-i}+t=k$ with $y_j>0$ for each $j$ and $t\ge0$.
$\hspace{.2 in}$Letting  $y_{n-i+1}=t+1$ gives 
$\hspace{.2 in}$$y_1+\cdots+y_{n-i+1}=k+1\;$ with $y_j>0$ for all $j$; so there are $\binom{k}{n-i}$ solutions.
This gives a total of $\displaystyle\sum_{i=0}^n 2^{n-i}\binom{n}{i}\binom{k}{n-i}$ solutions.
