1
$\begingroup$

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.

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

The generating function which you have found: $$ \left(\frac{1+x}{1-x}\right)^r $$ completely satisfy the restriction:

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

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. $$

I am not sure that this is a real simplification but it looks a little bit nicer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.