等比数列の和の公式を多変数に拡張
概要
突然ですが，次の問題を考えてみます．
袋の中に数字1が書かれたカードが1枚，2が書かれたカードが2枚，3が書かれたカードが3枚の，合計6枚のカードがある．袋からカードを無作為に取り出してもとに戻すという操作を繰り返し，取り出した数字が前に取り出した数字より小さくなったら操作を終了する．
操作が$n$回目まで続いている確率を求めよ．
$n$回目までに操作が続いており，$n$回目の時点で数字1を取り出した回数が$a$，数字2を取り出した回数が$b$，数字3を取り出した回数が$c$ ($a,b,c$は0以上の整数)となっている確率は，次のように表すことができます．
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
\left(\frac16\right)^a \left(\frac13\right)^b \left(\frac12\right)^c\ \ \ (a+b+c=n) \\
0\ \ \ \ \ \ \ (a+b+c\neq n)
\end{array}
\right.
\end{eqnarray}
$$
よって，$a+b+c=n$なる非負整数の組$(a,b,c)$すべてに対し$\left(\frac16\right)^a \left(\frac13\right)^b \left(\frac12\right)^c$の総和を求めればいいわけです．普通ならここで，
$$
\sum_{a=0}^{n} \sum_{b=0}^{n-a} \left(\frac16\right)^a \left(\frac13\right)^b \left(\frac12\right)^{n-a-b}
$$
と立式して，等比数列の和の公式，またはその変形である$ \sum_{k=0}^{n} x^k y^{n-k}=\frac{x^{n+1}-y^{n+1}}{x-y}\ (x\neq y)$を繰り返し用いて計算しますが，ちょっと計算が面倒くさいので，
$$
\sum_{a+b+c=n} \left(\frac16\right)^a \left(\frac13\right)^b \left(\frac12\right)^c
$$
を直接求める公式があったらいいなぁと思いまして，そのような公式を作ってみることにしました．
(ただし$\sum_{a+b+c=n}$は$a+b+c=n$なる非負整数の組$(a,b,c)$すべてに対しての総和を表す)
まずは3変数の場合を考えてみます．
$x,y,z$が相異なるとき，
$$
\sum_{a+b+c=n} x^a y^b z^c = \frac{x^{n+2}}{(x-y)(x-z)} + \frac{y^{n+2}}{(y-x)(y-z)} + \frac{z^{n+2}}{(z-x)(z-y)}
$$
証明は計算するだけです．
$$\sum_{a+b+c=n} x^a y^b z^c = \sum_{c=0}^{n} \sum_{a+b=n-c} x^a y^b z^c= \sum_{c=0}^{n} z^c \frac{x^{n-c+1}-y^{n-c+1}}{x-y}
$$
$$
= \frac{x}{x-y} \sum_{c=0}^n x^{n-c} z^{c} + \frac{y}{y-x} \sum_{c=0}^n y^{n-c} z^{c} = \frac{x}{x-y} \frac{x^{n+1}-z^{n+1}}{x-z} + \frac{y}{y-x} \frac{y^{n+1}-z^{n+1}}{y-z}
$$
$$
= \frac{x^{n+2}}{(x-y)(x-z)} + \frac{y^{n+2}}{(y-x)(y-z)} - z^{n+1}\left\{\frac x{(y-x)(y-z)}+\frac y{(x-y)(x-z)}\right\}
$$
$$
= \frac{x^{n+2}}{(x-y)(x-z)} + \frac{y^{n+2}}{(y-x)(y-z)} + \frac{z^{n+2}}{(z-x)(z-y)}
$$
これを使うと，問題1の答えは，
$$
\frac12\left(\frac16\right)^n-4\left(\frac13\right)^n+\frac92\left(\frac12\right)^n
$$
と求まります!
これを多変数に拡張した場合を考えてみます．次のように予想できます．
$m$を正の整数，$n$を負でない整数とする．相異なる数$x_1,x_2,\cdots,x_m$に対して，次の恒等式が成立する．
$$\sum_{p_1+p_2+\ldots+p_m=n}\prod_{k=1}^{m}x_k^{p_k}=\sum_{k=1}^{m}\frac{x_k^{n+m-1}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}$$
ただし$\sum_{p_1+p_2+\cdots+p_m=n}$は$p_1+p_2+\cdots+p_m=n$なる非負整数の組$(p_1,p_2,\cdots,p_m)$すべてに対しての総和を表し，$\prod_{j\neq k,1\le j\le m}$は$j\neq k,1\le j\le m$を満たす，すべての整数$j$に対しての積を表すものとします．$m=2,3,4$に対して具体的に書くと，次のようになります．
$$
\sum_{a+b=n} x^a y^b = \frac{x^{n+1}}{x-y} + \frac{y^{n+1}}{y-x}
$$
$$
\sum_{a+b+c=n} x^a y^b z^c = \frac{x^{n+2}}{(x-y)(x-z)} + \frac{y^{n+2}}{(y-x)(y-z)} + \frac{z^{n+2}}{(z-x)(z-y)}
$$
$$
\sum_{a+b+c+d=n} x^a y^b z^c w^d = \frac{x^{n+3}}{(x-y)(x-z)(x-w)} + \frac{y^{n+3}}{(y-x)(y-z)(y-w)} + \frac{z^{n+3}}{(z-x)(z-y)(z-w)}+ \frac{w^{n+3}}{(w-x)(w-y)(w-z)}
$$
(例1の$m=2$の場合に$y=1$を代入すれば，等比数列の和の公式になります)
繰り返し計算すれば示せそうに思えますが，実際はちょっとした工夫が必要になります．
証明
$m$を正の整数，$n$を整数とする．相異なる数$x_1,x_2,\cdots,x_m$に対して，$S_m(n)$を次のように定める．
$$S_m(n)=\sum_{k=1}^{m}\frac{x_k^{n+m-1}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}$$
先ほど予想した式の右辺にあたるものです．ここでは$n$を負を含む整数全体に拡張した式を$S_m(n)$としていることに注意してください．
$m\geq 2$のとき，漸化式
$$S_m\left(n\right)=S_{m-1}\left(n\right)+x_mS_m\left(n-1\right)$$
が成立する．
計算するだけです．
$$S_m\left(n\right)=\sum_{k=1}^{m}\frac{x_k^{n+m-1}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)} $$$$=\sum_{k=1}^{m-1}\frac{x_k^{n+m-2}}{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}\frac{x_k}{x_k-x_m}+\frac{x_m^{n+m-1}}{\prod_{1\le j\le m-1}\left(x_m-x_j\right)} $$$$=\sum_{k=1}^{m-1}\frac{x_k^{n+m-2}}{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}\left(1+\frac{x_m}{x_k-x_m}\right)+\frac{x_m^{n+m-1}}{\prod_{1\le j\le m-1}\left(x_m-x_j\right)} $$$$=\sum_{k=1}^{m-1}\frac{x_k^{n+m-2}}{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}+x_m\sum_{k=1}^{m}\frac{x_k^{n+m-2}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}=S_{m-1}\left(n\right)+x_mS_m\left(n-1\right)$$
$m\geq2かつ-m+1\le\ n\le-1$のとき
$$S_m\left(n\right)=0$$
が成立する．
次の2つを示せば帰納的に$m\geq2$かつ$-m+1\le\ n\le-1$の範囲での成立が示せる．
(1) $S_m\left(-m+1\right)=0\ \ (m\geq2)$
(2) $S_m\left(n-1\right)=0\land\ S_{m-1}\left(n\right)=0\Longrightarrow\ S_m\left(n\right)=0$
まず(1)を示す．
$$S_m\left(-m+1\right)=\sum_{k=1}^{m}\frac{1}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}
$$$$=-\sum_{k=1}^{m-1}\frac{1}{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}\frac{1}{x_m-x_k}+\frac{1}{\prod_{1\le j\le m-1}\left(x_m-x_j\right)}$$
ここで右辺を$x_m$を有理式とみて部分分数分解する．分母の次数が分子の次数より大きいので，定数$A_1,A_2,\cdots,A_{m-1}$に対し，
$$-\sum_{k=1}^{m-1}\frac{1}{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}\frac{1}{x_m-x_k}+\frac{1}{\prod_{1\le j\le m-1}\left(x_m-x_j\right)} = \sum_{k=1}^{m-1} \frac{A_k}{x_m-x_k}$$
と表すことができる．両辺に$x_m-x_k$をかけて，両辺の$x_m\rightarrow x_k$の極限をとると，
$$
-\frac1{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}+\frac1{\prod_{j\neq k,1\le j\le m-1}\left(x_k-x_j\right)}=A_k
$$
よって任意の$k$に対して$A_k=0$となることから，$S_m\left(-m+1\right)=0$が成り立つ．
次に(2)を示す．
補題2より，$$S_m\left(n\right)=S_{m-1}\left(n\right)+x_mS_m\left(n-1\right)$$がすべての整数$m,n$で成り立つので，$$S_m\left(n-1\right)=0\land\ S_{m-1}\left(n\right)=0\Longrightarrow\ x_mS_m\left(n-1\right)$$が成立する．
実は補題3だけでも結構面白い結果です．
$$
\frac{1}{(x-y)(x-z)} + \frac{1}{(y-x)(y-z)} + \frac{1}{(z-x)(z-y)}=0
$$
$$
\frac{x}{(x-y)(x-z)} + \frac{y}{(y-x)(y-z)} + \frac{z}{(z-x)(z-y)}=0
$$
$$
\frac{x^2}{(x-y)(x-z)(x-w)} + \frac{y^2}{(y-x)(y-z)(y-w)} + \frac{z^2}{(z-x)(z-y)(z-w)}+ \frac{w^2}{(w-x)(w-y)(w-z)} =0
$$
のような恒等式が次々と生み出せます．
$n\geq0$のとき，
$$S_m(n)=\sum_{k=1}^{m}\frac{x_k^{n+m-1}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}$$
$$T_m\left(n\right)=\sum_{p_1+p_2+\ldots+p_m=n}\prod_{k=1}^{m}x_k^{p_k}$$
に対し，$S_m\left(n\right)=T_m\left(n\right)$が成立する．
次の3つを示せば，帰納的に定理が正しいことが示される．
(1) $S_1\left(n\right)=T_1\left(n\right)$
(2) $S_m\left(0\right)=T_m\left(0\right)$
(3) $S_{m-1}\left(n\right)=T_{m-1}\left(n\right)\land\ S_m\left(n-1\right)=T_m\left(n-1\right)\Longrightarrow\ S_m\left(n\right)=T_m\left(n\right)$
(1)を示す．
$$S_1\left(n\right)=\sum_{k=1}^{1}\frac{x_k^n}{\prod_{j\neq k,1\le j\le1}\left(x_k-x_j\right)}=x_1^n=T_1\left(n\right)$$
よって成立．
(2)を示す
補題2，補題3より，
$$S_m\left(0\right)=S_{m-1}\left(0\right)+x_mS_m\left(-1\right)=S_{m-1}\left(0\right)$$
よって，$$S_m\left(0\right)=S_{m-1}\left(0\right)=\ldots=S_1\left(0\right)=T_1\left(0\right)=1=T_m(0)$$
(3)を示す．
補題2より$S_m\left(n\right)=S_{m-1}\left(n\right)+x_mS_m\left(n-1\right)$なので，$T_m\left(n\right)=T_{m-1}\left(n\right)+x_mT_m\left(n-1\right)$を満たすことを示せばよい．
$$T_m\left(n\right)=\sum_{p_1+p_2+\ldots+p_m=n}\prod_{k=1}^{m}x_k^{p_k}$$
について，$p_m=0$の項とそうでない項に分けると，
$$T_m\left(n\right)=\sum_{p_1+p_2+\ldots+p_{m-1}=n}\prod_{k=1}^{m-1}x_k^{p_k}+x_m\sum_{p_1^\prime+p_2^\prime+\ldots+p_m^\prime=n-1}\prod_{k=1}^{m}x_k^{p_k^\prime}$$
となる．よって，
$$T_m\left(n\right)=T_{m-1}\left(n\right)+x_mT_m\left(n-1\right)$$
以上より，定理は示された．
さいごに
恒等式
$$\sum_{p_1+p_2+\ldots+p_m=n}\prod_{k=1}^{m}x_k^{p_k}=\sum_{k=1}^{m}\frac{x_k^{n+m-1}}{\prod_{j\neq k,1\le j\le m}\left(x_k-x_j\right)}$$
の成立がわかりましたが，これが使えるのは$x_1,x_2,\cdots,x_m$が相異なるときであり，実際等しいものが含まれているときは使うことができません．その場合，ちょっと無理やりですが，極限を使って計算すればいいでしょう．
$x,y$が相異なるとき，
$$
\sum_{a+b+c=n} x^a y^{b+c}
$$
を求めたい．
$$
\sum_{a+b+c=n} x^a y^b z^c = \frac{x^{n+2}}{(x-y)(x-z)}+\frac{y^{n+2}}{(y-x)(y-z)}+\frac{z^{n+2}}{(z-x)(z-y)}
$$$$=\frac{x^{n+2}}{\left(x-y\right)\left(x-z\right)}+\frac{y^{n+2}\left(x-z\right)+z^{n+2}(y-x)}{(x-y)(y-z)(z-x)}
$$$$
=\frac{x^{n+2}}{\left(x-y\right)\left(x-z\right)}+\frac{y^{n+2}-z^{n+2}}{y-z}\frac{x}{\left(x-y\right)\left(z-x\right)}-\frac{y^{n+1}-z^{n+1}}{y-z}\frac{yz}{\left(x-y\right)\left(z-x\right)}$$$$\rightarrow\frac{x^{n+2}}{\left(x-y\right)\left(x-y\right)}+\frac{\left(n+2\right)y^{n+1}x}{\left(x-y\right)\left(y-x\right)}-\frac{\left(n+1\right)y^{n+2}}{\left(x-y\right)\left(y-x\right)}\ \ \ (z\rightarrow y)
$$$$
=\frac{x^{n+2}-\left(n+2\right)y^{n+1}x+(n+1)y^{n+2}}{\left(x-y\right)^2}
$$
より，
$$
\sum_{a+b+c=n} x^a y^{b+c}=\frac{x^{n+2}-\left(n+2\right)y^{n+1}x+(n+1)y^{n+2}}{\left(x-y\right)^2}
$$