総和とコンビネーションの証明

$$ \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より、
$$ \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} $$

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} $$