解説

方針・初手

$F_{n+1}(m)$ は $F_n(1),F_n(2),\ldots,F_n(m)$ の和で定義されている。したがって、$F_n(m)$ が二項係数で表せると仮定し、それを $k=1$ から $m$ まで和をとることで次の段階を示す。

そのために、次の二項係数の和の公式を用いる。

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+r}\mathrm{C}_{r+1} &= {}_{m+r+1}\mathrm{C}_{r+2} \end{aligned} $$

これはパスカルの公式から導ける。

解法1

まず、パスカルの公式

$$ \begin{aligned} {}_{a+1}\mathrm{C}_{b+1}-{}_{a}\mathrm{C}_{b+1} &= {}_{a}\mathrm{C}_{b} \end{aligned} $$

を用いる。$a=k+r,\ b=r+1$ とすれば、

$$ \begin{aligned} {}_{k+r+1}\mathrm{C}_{r+2}-{}_{k+r}\mathrm{C}_{r+2} &= {}_{k+r}\mathrm{C}_{r+1} \end{aligned} $$

である。よって、$k=1$ から $m$ まで和をとると、左辺は望ましい形に消去されて、

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+r}\mathrm{C}_{r+1} &= \sum_{k=1}^{m} \left\{ {}_{k+r+1}\mathrm{C}_{r+2}-{}_{k+r}\mathrm{C}_{r+2} \right\} \\ &= {}_{m+r+1}\mathrm{C}_{r+2}-{}_{r+1}\mathrm{C}_{r+2} \end{aligned}

$$

となる。ここで ${}_{r+1}\mathrm{C}_{r+2}=0$ であるから、

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+r}\mathrm{C}_{r+1} &= {}_{m+r+1}\mathrm{C}_{r+2} \end{aligned} $$

が成り立つ。

次に、$F_1(m)$ を二項係数で表す。

$$ \begin{aligned} F_1(m) &= \sum_{k=1}^{m}k \\ \frac{m(m+1)}{2} \\ {}_{m+1}\mathrm{C}_{2} \end{aligned} $$

である。

**(1)**

定義より、

$$ \begin{aligned} F_2(m) &= \sum_{k=1}^{m}F_1(k) \end{aligned} $$

である。いま

$$ F_1(k)={}_{k+1}\mathrm{C}_{2}

$$

だから、

$$ \begin{aligned} F_2(m) &= \sum_{k=1}^{m}{}_{k+1}\mathrm{C}_{2} \end{aligned} $$

となる。先ほどの公式で $r=1$ とすると、

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+1}\mathrm{C}_{2} &= {}_{m+2}\mathrm{C}_{3} \end{aligned} $$

である。したがって、

$$ F_2(m)={}_{m+2}\mathrm{C}_{3}

$$

が成り立つ。

**(2)**

定義より、

$$ \begin{aligned} F_3(m) &= \sum_{k=1}^{m}F_2(k) \end{aligned} $$

である。（1） より

$$ F_2(k)={}_{k+2}\mathrm{C}_{3}

$$

だから、

$$ \begin{aligned} F_3(m) &= \sum_{k=1}^{m}{}_{k+2}\mathrm{C}_{3} \end{aligned} $$

となる。先ほどの公式で $r=2$ とすると、

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+2}\mathrm{C}_{3} &= {}_{m+3}\mathrm{C}_{4} \end{aligned} $$

である。したがって、

$$ F_3(m)={}_{m+3}\mathrm{C}_{4}

$$

が成り立つ。

**(3)**

数学的帰納法により、

$$ F_n(m)={}_{m+n}\mathrm{C}_{n+1}

$$

を示す。

まず $n=1$ のとき、

$$ \begin{aligned} F_1(m) &= \sum_{k=1}^{m}k \\ {}_{m+1}\mathrm{C}_{2} \end{aligned} $$

である。これは

$$ {}_{m+n}\mathrm{C}_{n+1}

$$

に $n=1$ を代入したものと一致する。したがって、$n=1$ では成り立つ。

次に、ある自然数 $n$ について

$$ F_n(m)={}_{m+n}\mathrm{C}_{n+1}

$$

がすべての自然数 $m$ で成り立つと仮定する。

このとき、

$$ \begin{aligned} F_{n+1}(m) &= \sum_{k=1}^{m}F_n(k) \\ &= \sum_{k=1}^{m}{}_{k+n}\mathrm{C}_{n+1} \end{aligned}

$$

である。先ほどの公式で $r=n$ とすると、

$$ \begin{aligned} \sum_{k=1}^{m}{}_{k+n}\mathrm{C}_{n+1} &= {}_{m+n+1}\mathrm{C}_{n+2} \end{aligned} $$

だから、

$$ \begin{aligned} F_{n+1}(m) &= {}_{m+n+1}\mathrm{C}_{n+2} \end{aligned} $$

となる。これは

$$ \begin{aligned} F_{n+1}(m) &= {}_{m+(n+1)}\mathrm{C}_{(n+1)+1} \end{aligned} $$

と同じである。

よって、$n$ で成り立つなら $n+1$ でも成り立つ。数学的帰納法により、すべての自然数 $n,m$ について

$$ F_n(m)={}_{m+n}\mathrm{C}_{n+1}

$$

が成り立つ。

解説

この問題の中心は、和をとる操作が二項係数の下の数を $1$ 増やすことに対応している点である。

たとえば、

$$ F_1(m)={}_{m+1}\mathrm{C}_{2}

$$

から始めると、さらに和をとることで

$$ F_2(m)={}_{m+2}\mathrm{C}_{3}

$$

となり、もう一度和をとることで

$$ F_3(m)={}_{m+3}\mathrm{C}_{4}

$$

となる。

この規則を一般化したものが

$$ F_n(m)={}_{m+n}\mathrm{C}_{n+1}

$$

である。単に形を予想するだけでなく、パスカルの公式による和の公式を使って帰納法で示すことが重要である。

答え

**(1)**

$$ F_2(m)={}_{m+2}\mathrm{C}_{3}={}_{m+2}C_3

$$

**(2)**

$$ F_3(m)={}_{m+3}\mathrm{C}_{4}={}_{m+3}C_4

$$

**(3)**

すべての自然数 $n,m$ について、

$$ F_n(m)={}_{m+n}\mathrm{C}_{n+1}

$$

が成り立つ。