# Can the expression $\sum_{i=0}^{r} {r\choose i}{n-i+r-1\choose r-1}$ be simplified?

The problem originally was:

Let $$r$$ be a positive integer, and $$p_n$$ the number of solutions to the equation: $$|x_1|+|x_2|+...+|x_r|=n$$ when $$x_k$$ may be positive, negative or zero.

Find the generating function of $$p_n$$. The function should be written explicitly (for example, not as a multiplication of two infinite series).

What I did is:

$$(1+2x+2x^2+...)^r=(\frac{1}{1-x}+\frac{x}{1-x})^r=(\frac{1+x}{1-x})^r=\sum_{i=0}^{\infty} \sum_{j=0}^{\infty}{r\choose i}{j+r-1\choose r-1}x^{i+j}$$

Now, for $$i+j=n$$, we get that the coefficient of $$x^n$$ is: $$\sum_{i=0}^{\infty} {r\choose i}{n-i+r-1\choose r-1} = \sum_{i=0}^{r} {r\choose i}{n-i+r-1\choose r-1}$$ Something that I am not able to simplify, and I am afraid that my answer (if correct) does not meet the criteria posed in the question.

I have tried to mess around with the expression but couldn't really simplify it.

Any insight will be appreciated.

• What is $n$ in your $\sum_{i=0}^\infty \sum_{j=0}^\infty \cdots$? – kccu May 16 at 19:12
• My bad I mixed some things up. It is supposed to be fixed now. – איתן לוי May 16 at 19:18
• So then the later binomial coefficient should be $\binom{n-i+r-1}{r-1}$? – kccu May 16 at 19:20
• Why do you dislike the function $\left(\frac {1+x}{1-x} \right )^r$? – user May 16 at 19:32
• I dislike it because it is impossible to tell what is the coefficient of $x^n$ by looking at it. – איתן לוי May 16 at 19:45

The generating function which you have found: $$\left(\frac{1+x}{1-x}\right)^r$$ completely satisfy the restriction:
What concerns your main question I can suggest another representation of the sum: $$\sum_{i=0}^r\binom ri\binom{n-i+r-1}{r-1}=\sum_{i=1}^r\binom ri\binom{n-1}{i-1}2^i.$$