1

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

175
0
$$$$
パスカルの三角形

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

投稿日:2023514
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

12匁
12匁
2
1523
直和の定義見て"集合として等しい"を知らずに背伸びしていたことに気づいたことがある。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中