せんべい分割問題の解答例を示します。
解3:漸化式を使う。
分割の数をh(n)とする。
n-1回の切断が行われたところにn回目の切断を行う。このとき、n回目の切断線はn-1回の切断線と交わり、新たに n個の断片が作られる。
h(n) = h(n-1)+n
したがって、h(n) = h(n-1)+n
= n+(n-1)+(n-2)+…+2+2
= n(n+1)/2+1
= (n2+n+2)/2
(注意)h(n) = (n2+n+2)/2 = C(n,0)+C(n,1)+C(n,2) とも書ける。
ただし、C(n,r)は2項係数。