Stuck on the probability of rolling 'p' with 'n' s-sided dice

[Potatochip911]

TL;DR

Having trouble with math involving two series being multiplied together.

Hi, I've been following the derivation of wolfram mathworld for this problem and I'm running into some trouble regarding the summation indices. Currently I am at the step where we have found that (it's pretty much just binomial expansion and taylor series to get to this point)

$$ f(x) = x^n\left[\sum_{k=0}^{\infty}\binom{n}{k}(-1)^kx^{sk}\right ]\sum_{l=0}^\infty\binom{n+l-1}{l}x^l $$

Now we're interested in finding the coefficient for the term $x^p$ to find how many possibilities there are to obtain that exponent $p$. This gives the equality $$p = n + sk + l$$ which we can use to put $l$ in terms of $k$ in the 2nd summation via $$l = p-n-sk$$

This gives

$$x^n\left[\sum_{k=0}^{\infty}\binom{n}{k}(-1)^kx^{sk}\right ]\sum_k \binom{p-sk-1}{p-sk-n}x^{p-n-sk} $$

For the new summation indices we have $k = (p-n-l)/s$, plugging in $l=0$ and $l=\infty$ gives lower index $(p-n)/s$ and upper index $-\infty$ which doesn't make sense. On wolfram they are just claiming that the coefficient of $x^p$ is given by

$$c = \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{p-sk-1}{p-sk-n}$$

I'm having trouble understanding this as they are simply multiplying the coefficients for the two different series together. If we consider as an example:

$$\sum_{k=0}^1\binom{3}{k}x^k\sum_{k=0}^1\binom{2}{k}x^k=(1+3x)(1+2x)=1+(3+2)x+6x^2 = 1+5x+6x^2$$

then multiplying the coefficients together only results in the correct coefficient for their proposed solution when there are no "interfering" (idk the proper math word) terms.

To summarize, I'm having trouble understanding how in their solution they don't change the limits of the sum by plugging in $l$, and I'm also confused by the logic/math surrounding the coefficient of $x^p$.

 

[fresh_42]

Let us assume that $k\leq n$ has to hold for possible indices $l$.

Then $0\leq k \leq n$ and thus $p-n \leq l=p-n-sk \leq p-n-sn$ which gives the claimed boundaries.

Now we check whether they match. Therefore we must check $l+sk+n = p$.
Our value for $l$ at position $k$ is $l=p-sk-n$ (formula for c), hence $(p-sk-n)+sk+n=p$ holds.

 

[Potatochip911]

Let us assume that $k\leq n$ has to hold for possible indices $l$.

Then $0\leq k \leq n$ and thus $p-n \leq l=p-n-sk \leq p-n-sn$ which gives the claimed boundaries.

I'm still finding this quite confusing. I understand what you're saying here that these are the boundaries for $l$ using $k$. Then it seems like the last summation can be written as

$$
\sum_{l=p-n}^{p-n-sn}\binom{p-sk-1}{p-sk-n}x^{p-sk-n}
$$

but since $l$ has been replaced we also need to replace the summation index now using $l=p-sk-n$ which results in

$$
p-sk-n=p-n\Rightarrow k=0 \mbox{, for the lower bound} \\
p-sk-n=p-n-sn\Rightarrow k=n\mbox{, for the upper bound}
$$

so the last sum can now be rewritten as

$$
\sum_{k=0}^n \binom{p-sk-1}{p-sk-n}x^{p-sk-n}
$$

Returning to the original expression (I accidentally had the first sum going to infinity in the orginal post)

$$
x^n\left [\sum_{k=0}^{n}\binom{n}{k}(-1)^kx^{sk}\right ] \sum_{k=0}^n\binom{p-sk-1}{p-sk-n}x^{p-sk-n}
$$

but $x^p$ and $x^{-n}$ are independent of the index $k$ therefore we can pull them out resulting in

$$
x^n\cdot x^{p-n}\left [\sum_{k=0}^{n}\binom{n}{k}(-1)^kx^{sk}\right ] \sum_{k=0}^n\binom{p-sk-1}{p-sk-n}x^{-sk} \\

= x^p\left [\sum_{k=0}^{n}\binom{n}{k}(-1)^kx^{sk}\right ] \sum_{k=0}^n\binom{p-sk-1}{p-sk-n}x^{-sk}
$$

Now I'm still struggling to see why we can just take the coefficients from two different sums.

Edit: Ok I see the key insight now. Since we have $x^p$ factored out on the outside then the only terms that will stay at $x^p$ will be terms with $x^0$ which happens when $k$ in the first sum equals $k$ in the second sum. Now it's clear the coefficient is given by $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{p-sk-1}{p-sk-n}$

Now I'm just stuck understanding this last step that since $p-sk-n>0$ only when $k <(p-n)/s$ that $$\binom{p-sk-1}{p-sk-n} = \binom{p-sk-1}{n-1}$$

 

[fresh_42]

Let's write it this way:
\begin{align*}
f(x)&=\left( \sum_{k=0}^\infty a_kx^{n+sk} \right)\cdot \left( \sum_{l=0}^\infty b_lx^l \right)\\
&= \sum_{k,l = 0}^\infty a_kb_lx^{n+sk+l}\\
&=\sum_{p=0}^\infty \sum_{n+sk+l=p} a_kb_lx^p\\
&=\sum_{p=0}^\infty x^p \left( \sum_{k=0}^n \underbrace{ a_kb_{\underbrace{p-n-sk}_{\text{ former }l}} }_{=c_k} \right)
\end{align*}
Now what's left to calculate is
\begin{align*}
c_k&=a_k \cdot b_{p-n-sk}\\&=(-1)^k\cdot \binom{n}{k} \cdot \binom{n+(p-n-sk)-1}{p-n-sk}\\&=(-1)^k\cdot \binom{n}{k} \cdot \binom{p-sk-1}{p-sk-n}
\end{align*}
and $c=c_p=\sum_{k=0}^n c_k$