Pascal's rule

Algebraic proof

Alternatively, the algebraic derivation of the binomial case follows. $${\displaystyle \begin{array}{cc}(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1})& =\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\\ & =(n-1)!\left[\frac{n-k}{k!(n-k)!}+\frac{k}{k!(n-k)!}\right]\\ & =(n-1)!\frac{n}{k!(n-k)!}\\ & =\frac{n!}{k!(n-k)!}\\ & =(\genfrac{}{}{0ex}{}{n}{k}).\end{array}}$$

An alternative algebraic proof using the alternative definition of binomial coefficients: ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\cdots (n-k+1)}{k!}}$. Indeed

$${\displaystyle \begin{array}{cc}(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1})& =\frac{(n-1)\cdots ((n-1)-k+1)}{k!}+\frac{(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}\\ & =\frac{(n-1)\cdots (n-k)}{k!}+\frac{(n-1)\cdots (n-k+1)}{(k-1)!}\\ & =\frac{(n-1)\cdots (n-k+1)}{(k-1)!}\left[\frac{n-k}{k}+1\right]\\ & =\frac{(n-1)\cdots (n-k+1)}{(k-1)!}\cdot \frac{n}{k}\\ & =\frac{n(n-1)\cdots (n-k+1)}{k!}\\ & =(\genfrac{}{}{0ex}{}{n}{k}).\end{array}}$$

Since ${\displaystyle (\genfrac{}{}{0ex}{}{z}{k})=\frac{z(z-1)\cdots (z-k+1)}{k!}}$ is used as the extended definition of the binomial coefficient when z is a complex number, thus the above alternative algebraic proof shows that Pascal's rule holds more generally when n is replaced by any complex number.

Generalization

Pascal's rule can be generalized to multinomial coefficients. For any integer p such that ${\displaystyle p\ge 2}$, ${\displaystyle k_1,k_2,k_3,\dots ,k_p\in {\mathbb{Z}}^{+},}$ and ${\displaystyle n=k_1+k_2+k_3+\cdots +k_p\ge 1}$, $${\displaystyle (\genfrac{}{}{0ex}{}{n-1}{k_1-1,k_2,k_3,\dots ,k_p})+(\genfrac{}{}{0ex}{}{n-1}{k_1,k_2-1,k_3,\dots ,k_p})+\cdots +(\genfrac{}{}{0ex}{}{n-1}{k_1,k_2,k_3,\dots ,k_p-1})=(\genfrac{}{}{0ex}{}{n}{k_1,k_2,k_3,\dots ,k_p})}$$ where ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k_1,k_2,k_3,\dots ,k_p})}$ is the coefficient of the ${\displaystyle x_1^{k_1}{x}_2^{k_2}\cdots x_p^{k_p}}$ term in the expansion of ${\displaystyle (x_1+x_2+\cdots +x_p{)}^n}$.

The algebraic derivation for this general case is as follows. Let p be an integer such that ${\displaystyle p\ge 2}$, ${\displaystyle k_1,k_2,k_3,\dots ,k_p\in {\mathbb{N}}^{+},}$ and ${\displaystyle n=k_1+k_2+k_3+\cdots +k_p\ge 1}$. Then $${\displaystyle \begin{array}{cc}& (\genfrac{}{}{0ex}{}{n-1}{k_1-1,k_2,k_3,\dots ,k_p})+(\genfrac{}{}{0ex}{}{n-1}{k_1,k_2-1,k_3,\dots ,k_p})+\cdots +(\genfrac{}{}{0ex}{}{n-1}{k_1,k_2,k_3,\dots ,k_p-1})\\ & =\frac{(n-1)!}{(k_1-1)!k_2!k_3!\cdots k_p!}+\frac{(n-1)!}{k_1!(k_2-1)!k_3!\cdots k_p!}+\cdots +\frac{(n-1)!}{k_1!k_2!k_3!\cdots (k_p-1)!}\\ & =\frac{k_1(n-1)!}{k_1!k_2!k_3!\cdots k_p!}+\frac{k_2(n-1)!}{k_1!k_2!k_3!\cdots k_p!}+\cdots +\frac{k_p(n-1)!}{k_1!k_2!k_3!\cdots k_p!}=\frac{(k_1+k_2+\cdots +k_p)(n-1)!}{k_1!k_2!k_3!\cdots k_p!}\\ & =\frac{n(n-1)!}{k_1!k_2!k_3!\cdots k_p!}=\frac{n!}{k_1!k_2!k_3!\cdots k_p!}=(\genfrac{}{}{0ex}{}{n}{k_1,k_2,k_3,\dots ,k_p}).\end{array}}$$