京都大学 1979年 文系 第3問 解説

方針・初手

与えられた規則を数式（漸化式）に翻訳し、数学的帰納法を用いて等式を証明する。 数列の規則は、「上の行の隣り合う2つの項の和が、下の行の項になる」という、いわゆるパスカルの三角形と同様の構造を持っている。 規則を式で表すと、第 $n$ 行の数列 ${}_nA_k$ $(k=0, 1, \dots, n+2)$ について以下が成り立つ。

• （ア） $n=1$ のとき、${}_1A_0=1, {}_1A_1=1, {}_1A_2=1, {}_1A_3=1$
• （イ） 第 $n+1$ 行の両端の数は $1$ であるから、 ${}_{n+1}A_0 = 1$ ${}_{n+1}A_{n+3} = 1$ 両端以外の数は左上の数と右上の数の和であるから、$1 \leqq k \leqq n+2$ に対して ${}_{n+1}A_k = {}_nA_{k-1} + {}_nA_k$

この漸化式を用いて、数学的帰納法で証明を行う。あるいは、二項定理を用いて式を展開し、その係数が規則を満たすことを直接示す別解も有効である。

解法1

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

$$ (1+x^2)(1+x)^n = \sum_{k=0}^{n+2} {}_nA_k x^k \quad \cdots (*) $$

が成り立つことを数学的帰納法によって示す。

(I) $n=1$ のとき

等式 $(*)$ の左辺は

$$ (1+x^2)(1+x)^1 = 1 + x + x^2 + x^3 $$

となる。 一方、等式 $(*)$ の右辺は

$$ \sum_{k=0}^{3} {}_1A_k x^k = {}_1A_0 + {}_1A_1 x + {}_1A_2 x^2 + {}_1A_3 x^3 $$

となる。 規則 (ア) より ${}_1A_0=1, {}_1A_1=1, {}_1A_2=1, {}_1A_3=1$ であるから、右辺は $1 + x + x^2 + x^3$ となり、左辺と一致する。 よって、$n=1$ のとき $(*)$ は成り立つ。

(II) $n=m$ のとき $(*)$ が成り立つと仮定する

すなわち、

$$ (1+x^2)(1+x)^m = \sum_{k=0}^{m+2} {}_mA_k x^k $$

が成り立つと仮定する。 このとき、$n=m+1$ における $(*)$ の左辺を変形すると、

$$ (1+x^2)(1+x)^{m+1} = (1+x)(1+x^2)(1+x)^m $$

仮定を用いて右辺の形に置き換えると、

$$ (1+x) \sum_{k=0}^{m+2} {}_mA_k x^k = \sum_{k=0}^{m+2} {}_mA_k x^k + x \sum_{k=0}^{m+2} {}_mA_k x^k $$

$$ = \sum_{k=0}^{m+2} {}_mA_k x^k + \sum_{k=0}^{m+2} {}_mA_k x^{k+1} $$

ここで、第2項の和の添字を調整するため $j=k+1$ とおくと、$k=0$ のとき $j=1$、$k=m+2$ のとき $j=m+3$ となるので、

$$ = \sum_{k=0}^{m+2} {}_mA_k x^k + \sum_{j=1}^{m+3} {}_mA_{j-1} x^j $$

和の変数を $k$ に統一し、初項と末項を和の記号から外して整理する。

$$ = \left( {}_mA_0 + \sum_{k=1}^{m+2} {}_mA_k x^k \right) + \left( \sum_{k=1}^{m+2} {}_mA_{k-1} x^k + {}_mA_{m+2} x^{m+3} \right) $$

$$ = {}_mA_0 + \sum_{k=1}^{m+2} ({}_mA_k + {}_mA_{k-1}) x^k + {}_mA_{m+2} x^{m+3} $$

ここで、規則 (イ) を確認する。 ${}_mA_0$ は第 $m$ 行の左端の数なので ${}_mA_0 = 1$ であり、第 $m+1$ 行の左端の数 ${}_{m+1}A_0$ も $1$ であるから、${}_mA_0 = {}_{m+1}A_0$ である。 同様に、${}_mA_{m+2}$ は第 $m$ 行の右端の数なので ${}_mA_{m+2} = 1$ であり、第 $m+1$ 行の右端の数 ${}_{m+1}A_{m+3}$ も $1$ であるから、${}_mA_{m+2} = {}_{m+1}A_{m+3}$ である。 さらに、その他の数は左上の数と右上の数の和であるから、$1 \leqq k \leqq m+2$ において ${}_{m+1}A_k = {}_mA_{k-1} + {}_mA_k$ が成り立つ。

これらを代入すると、

$$ = {}_{m+1}A_0 + \sum_{k=1}^{m+2} {}_{m+1}A_k x^k + {}_{m+1}A_{m+3} x^{m+3} $$

$$ = \sum_{k=0}^{m+3} {}_{m+1}A_k x^k $$

となり、これは $(*)$ において $n=m+1$ とした式の右辺と一致する。 よって、$n=m+1$ のときも $(*)$ は成り立つ。

(I), (II) より、すべての自然数 $n$ について

$$ (1+x^2)(1+x)^n = \sum_{k=0}^{n+2} {}_nA_k x^k $$

が成り立つことが示された。

解法2

$(1+x^2)(1+x)^n$ を展開したときの $x^k$ の係数を $C_{n,k}$ と定義し、この係数が問題文の規則 (ア) および (イ) を満たすことを示す。 二項定理より、

$$ (1+x)^n = \sum_{i=0}^n {}_n\mathrm{C}_{i} x^i $$

である。（ただし、$i<0$ または $i>n$ のとき ${}_n\mathrm{C}_{i} = 0$ と定める）

これを $(1+x^2)(1+x)^n$ に代入すると、

$$ (1+x^2)(1+x)^n = (1+x^2) \sum_{i=0}^n {}_n\mathrm{C}_{i} x^i $$

$$ = \sum_{i=0}^n {}_n\mathrm{C}_{i} x^i + \sum_{i=0}^n {}_n\mathrm{C}_{i} x^{i+2} $$

第2項の和の添字を $k=i+2$ と変換して整理すると、$x^k$ の係数 $C_{n,k}$ は以下のように表せる。

$$ C_{n,k} = {}_n\mathrm{C}_{k} + {}_n\mathrm{C}_{k-2} $$

（多項式の最高次は $x^{n+2}$ であるから、$k$ は $0 \leqq k \leqq n+2$ の範囲をとる）

この係数 $C_{n,k}$ が与えられた規則を満たすことを確認する。

(ア) 第1行について ($n=1$ のとき) $C_{1,k} = {}_1\mathrm{C}_{k} + {}_1\mathrm{C}_{k-2}$ に $k=0, 1, 2, 3$ を代入する。 $C_{1,0} = {}_1\mathrm{C}_{0} + {}_1\mathrm{C}_{-2} = 1 + 0 = 1$ $C_{1,1} = {}_1\mathrm{C}_{1} + {}_1\mathrm{C}_{-1} = 1 + 0 = 1$ $C_{1,2} = {}_1\mathrm{C}_{2} + {}_1\mathrm{C}_{0} = 0 + 1 = 1$ $C_{1,3} = {}_1\mathrm{C}_{3} + {}_1\mathrm{C}_{1} = 0 + 1 = 1$ となり、第1行の数列 $1, 1, 1, 1$ と一致する。

(イ) 第2行以降について ($n \geqq 1$ のとき) 左右両端の数について、 左端：$C_{n+1,0} = {}_{n+1}\mathrm{C}_{0} + {}_{n+1}\mathrm{C}_{-2} = 1 + 0 = 1$ 右端：$C_{n+1,n+3} = {}_{n+1}\mathrm{C}_{n+3} + {}_{n+1}\mathrm{C}_{n+1} = 0 + 1 = 1$ となり、両端の数は常に $1$ である。

次に、隣り合う項の和について考える。 パスカルの三角形の性質から、任意の自然数 $n$ と整数 $k$ について ${}_{n+1}\mathrm{C}_{k} = {}_n\mathrm{C}_{k} + {}_n\mathrm{C}_{k-1}$ が成り立つことを用いる。

$$ C_{n+1,k} = {}_{n+1}\mathrm{C}_{k} + {}_{n+1}\mathrm{C}_{k-2} $$

$$ = ({}_n\mathrm{C}_{k} + {}_n\mathrm{C}_{k-1}) + ({}_n\mathrm{C}_{k-2} + {}_n\mathrm{C}_{k-3}) $$

和の順序を入れ替えて組み合わせると、

$$ = ({}_n\mathrm{C}_{k} + {}_n\mathrm{C}_{k-2}) + ({}_n\mathrm{C}_{k-1} + {}_n\mathrm{C}_{k-3}) $$

定義より、この右辺は $C_{n,k} + C_{n,k-1}$ と等しい。したがって、

$$ C_{n+1,k} = C_{n,k} + C_{n,k-1} $$

が成り立つ。これは「左上の数と右上の数の和が下の数になる」という規則 (イ) を表している。

以上より、展開式の係数 $C_{n,k}$ は数列 ${}_nA_k$ の規則をすべて満たす。 初期状態が等しく、漸化式も等しいことから、数列は一意に定まり、係数 $C_{n,k}$ は ${}_nA_k$ と完全に一致する。 したがって、

$$ (1+x^2)(1+x)^n = \sum_{k=0}^{n+2} {}_nA_k x^k $$

が成り立つことが示された。

解説

「母関数（生成関数）」の考え方を背景に持つ問題である。 数列に対して、その各項を係数に持つような多項式（または冪級数）を考えることで、数列の性質を多項式の計算に帰着させることができる。 「隣り合う項を足して下の行を作る」というパスカルの三角形の操作は、母関数の世界では「$(1+x)$ を掛ける」という操作に対応している。本問では初期状態（第1行）が $1,1$ ではなく $1,1,1,1$ であるため、対応する多項式が $1+x+x^2+x^3 = (1+x^2)(1+x)$ になっている点がポイントである。

答え

略（解法1の証明を参照）