数学的帰納法であみだくじが全通り可能なことを証明する

あみだくじ、全てのスタート地点から全てのエンド地点を結ぶ全通りの組み合わせが実現可能であることを証明する。

概要

1. P(1)は1本のあみだくじなので自明である
2. P(n)を真と仮定する
3. P(n+1)はP(n)の左右どちらかに1本足した形になる
4. 仮に左に足したとして、足した1本以外の組み合わせは真となるので、足した1本をそれ以外の全ての場所に落とせればよい
5. この時、一番右に落とすパターン以外は右に1本足した場合のP(n)に含まれるため真。
6. つまり、左端から右端に落とすパターンを証明する。
7. これは、左端から階段上に右端まで棒を引いていけば良いので真となる。
8. この時残りn本の線は、元のn+1本のあみだくじと左に1本分ずらしたものと同じになる。
9. これは、P(n)と同じ形になるので真。
10. 証明終わり