総和とコンビネーションの証明
$$ 1\leq r \leq n \Longrightarrow { n \choose r}={n-1 \choose r-1}+{ n-1 \choose r} $$
$$ \begin{eqnarray} {n-1 \choose r-1}+{ n-1 \choose r} &=& \frac{\left( n-1 \right)!}{\left( r-1 \right) ! \left( n-r \right) !}+ \frac{\left( n-1 \right) !}{\left( r \right) !\left( n-r-1 \right) !} \\ &=& \frac{\left( n-1 \right)!}{\left( r-1 \right) ! \left( n-r-1 \right) ! \left( n-r \right)}+ \frac{\left( n-1 \right) !}{\left( r-1 \right) !\left( n-r-1 \right) ! \left( r \right)} \\ &=& \frac{\left( n-1 \right)! \left( r \right) + \left( n-1 \right) ! \left( n-r \right)}{\left( r-1 \right) ! \left( n-r-1 \right) ! \left( n-r \right) \left( r \right)} \\ &=& \frac{\left( n-1 \right) ! \left( n \right)}{\left( r-1 \right) ! \left( r \right) \left( n-r-1 \right) ! \left( n-r \right)} \\ &=& \frac{n !}{r ! \left( n-r \right)} \\ &=& { n \choose r} \end{eqnarray} $$
$$ 1+l=i \Longrightarrow \sum_{k=1}^{n}{k+l \choose i}={ n+l+1 \choose 1+i}$$
補題1より、
$$
\begin{eqnarray}
{ n+l+1 \choose 1+i}
&=& { n+l \choose i} + { n+l \choose 1+i} \\
&=& { n+l \choose i} + { n+l-1 \choose i} + {n+l-1 \choose 1+i} \\
&=& { n+l \choose i} + { n+l-1 \choose i} + {n+l-2 \choose i} + {n+l-2 \choose 1+i} \\
\cdots \\
&=& { n+l \choose i} + { n+l-1 \choose i} + {n+l-2 \choose i} + \cdots + {2+l \choose i} + {2+l \choose 1+i} \\
1+l=i \Longleftrightarrow 2+l=1+i より \\
&=& { n+l \choose i} + { n+l-1 \choose i} + {n+l-2 \choose i} + \cdots + {2+l \choose i} + 1 \\
&=& { n+l \choose i} + { n+l-1 \choose i} + {n+l-2 \choose i} + \cdots + {2+l \choose i} + {1+l \choose i} \\
&=& \sum_{k=1}^{n}{ k+l \choose i}
\end{eqnarray}
$$
任意の$n,i$に対して以下が成り立つ.
$$
\begin{eqnarray}
\sum_{k_{1}=1}^{n}(\sum_{k_{2}=1}^{k_{1}}(\cdots(\sum_{k_{i}=1}^{k_{i-1}}k_{i}))) &=& { n+i \choose 1+i}
\end{eqnarray}
$$
1.i=1 の場合
$$
\begin{eqnarray}
\sum_{k_{1}=1}^{n}k_{1}
&=& \frac{1}{2}n(n+1)
&=& { n+1 \choose 2 }
&=& { n+i \choose 1+i}
\end{eqnarray}
$$
2.iで成り立つと仮定し、i+1 の場合
$$
\begin{eqnarray}
\sum_{k_{1}=1}^{n}(\sum_{k_{2}=1}^{k_{1}}(\cdots(\sum_{k_{i+1}=1}^{k_{i}}k_{i+1})))
&=& \sum_{k_{i+1}=1}^{n}(\sum_{k_{i}=1}^{k_{i+1}}(\cdots(\sum_{k_{1}=1}^{k_{2}}k_{1})))
&=& \sum_{k_{i+1}=1}^{n}{ k_{i+1}+i \choose 1+i }
&=&{ n+(i+1) \choose 1+(i+1)}
\end{eqnarray}
$$
