山分け問題(1)の解答例を示します。
問題(1)の解1
数学的帰納法で示す。
求める総和をf(n)=n(n-1)/2と仮定する。
(A)n=2の時、f(2)=1となり、明らか。
(B)n≦k のとき成り立つと仮定し、n=k+1のときを考える。
石の数k+1個の山を、mとk+1-mに分ける。1≦m≦k。
f(k+1) = m(k+1-m) + f(m) + f(k+1-m)
= m(k+1-m) + m(m-1)/2 + (k+1-m)(k-m)/2
= (k+1)k/2
(A),(B)により、命題は示された。