¿Puedes demostrar esta afirmación de lanzamiento de dados recursivos múltiples de $n$ lados?

Question

Sea $W_{s,r,n}$ el número total de formas en que la suma $s$ puede mostrarse después de lanzar $r$ dados de $n$ caras. Definimos

$$W_{s,0,n} = \begin{cases} 1, & \text{si s = 0} \\ 0, & \text{si s $\neq$ 0} \\ \end{cases} $$

para todo $s \in \mathbb Z$ y $n \in \mathbb N^*$. ¿Puedes demostrar que

$$W_{s,r,n} =W_{s-1,r,n} + W_{s-1,r-1,n} - W_{s-(1+n),r-1,n}$$

para todo $s \in \mathbb Z$, $r \in \mathbb N^*$ y $n \in \mathbb N^*$?

Answer 1

Consideras los dados como distinguibles, por lo que por ejemplo $1+5+6+6$ es distinto de $6+5+1+6$. Por lo tanto, $\displaystyle W_{s,r,n} = \sum_{j=1}^n W_{s-j,r-1,n}$.

Hay una demostración por inducción:

Caso base: para $r=1$ la recurrencia se satisface por $$W_{s,1,n} = \begin{cases} 1, & \text{ si } 1 \le s \le n \\ 0, & \text{ si } s \le 0 \text{ o } s \ge n+1 \\ \end{cases}$$

Caso inductivo: si es cierto hasta $r-1$ dados entonces

$$W_{s,r,n} = \sum_{j=1}^n W_{s-j,r-1,n} = \sum_{j=1}^n \left(W_{s-j-1,r-1,n} + W_{s-j-1,r-2,n} - W_{s-j-(1+n),r-2,n}\right)$$ $$= \sum_{j=1}^n W_{s-j-1,r-1,n} + \sum_{j=1}^n W_{s-j-1,r-2,n} - \sum_{j=1}^n W_{s-j-(1+n),r-2,n} $$ $$= W_{s-1,r,n} + W_{s-1,r-1,n} - W_{s-(1+n),r-1,n}$$

por lo tanto es cierto hasta $r$ dados, y por lo tanto para cualquier número positivo de dados.