How many solutions over $\mathbb{Z}$ to the equation $|x_1|+|x_2|+|x_3|+\dots+|x_{k-1}|+ |x_k|= n$?
Notes:
The order does matter. For instance, $1+2+3$ is different from $3+2+1$.
To avoid misunderstandings - $|x_1|$ denotes absolute value and $0 \in \mathbb{Z}$.
Please any help. I honestly don't know how to approach this one. Thank you
On
As a start, if $k=2$: $$\begin{align} (0,-1),(-1,0) \ \ & | 1 | \ \ (0,1),(1,0); \\ (-2,0),(-1,1),(1,-1),(0,-2) \ \ & | 2 | \ \ (0,2),(1,1),(2,0); \\ (-3,0),(-2,1),(-1,2),(0,-3),(1,-2),(2,-1) \ \ & | 3 | \ \ (0,3),(1,2),(2,1),(3,0); \\ \cdots \\ 2n \ \ | n | \ \ n+1 \Rightarrow 3n+1. \end{align}$$
The solution for positive integer ${<}x_i{>}$ is relatively simple; inserting $k{-}1$ separators into $n{-}1$ gaps, $\binom {n-1}{k-1}$. Then allow those integers to be negative producing a multiple of $2^k$.
Then we have to allow the ${<}x_i{>}$ to also be zero; between $1$ and $k{-}1$ of them. So we choose the zero elements, then repeat the above calculation, and sum across all those.
This gives $$\sum_{i=0}^{k-1} \binom ki \cdot 2^{k-i} \cdot \binom {n-1}{k-i-1}$$