数列の問題

階差の記号 数列 $\{a_k\}$ $(k=0,1,2,\dots )$ に対し、その階差数列を $\Delta a_k=a_{k+1}-a_k$ と書き、さらに階差をとったものを ${\Delta }^2{a}_k=\Delta a_{k+1}-\Delta a_k$、一般に ${\Delta }^{j+1}{a}_k={\Delta }^j{a}_{k+1}-{\Delta }^j{a}_k$ と書く（${\Delta }^0{a}_k=a_k$）。

鍵になる式 どんな数列についても、すべての $m\geqq 0$ で
$$a_m=\sum _{j=0}^m{}_m{\mathrm{C}}_j{\Delta }^j{a}_0(1)$$
が成り立つ。$m$ についての数学的帰納法で示す。$m=0$ では $a_0={\Delta }^0{a}_0$ で成り立つ。ある $m$ ですべての数列について $(1)$ が成り立つとすると、数列 $\{\Delta a_k\}$ にも $(1)$ を使えて $\Delta a_m=\sum _{j=0}^m{}_m{\mathrm{C}}_j{\Delta }^{j+1}{a}_0$ なので
$$a_{m+1}=a_m+\Delta a_m=\sum _{j=0}^m{}_m{\mathrm{C}}_j{\Delta }^j{a}_0+\sum _{j=1}^{m+1}{}_m{\mathrm{C}}_{j-1}{\Delta }^j{a}_0=\sum _{j=0}^{m+1}{}_{m+1}{\mathrm{C}}_j{\Delta }^j{a}_0$$
（${}_m{\mathrm{C}}_j+{}_m{\mathrm{C}}_{j-1}={}_{m+1}{\mathrm{C}}_j$ を使った。${}_m{\mathrm{C}}_{-1}={}_m{\mathrm{C}}_{m+1}=0$ とする）。よって $(1)$ は $m+1$ でも成り立つ。

$a_k=P(k)$ に当てはめる $a_k=P(k)$ とおく。

(i) $j\leqq n$ のとき ${\Delta }^j{a}_0=2^j$ である。実際、${\Delta }^j{a}_0$ は $a_0,a_1,\dots ,a_j$ だけから計算される（階差を $1$ 回とるごとに使う項が $1$ つずつ右へ広がるだけ）。$j\leqq n$ ならこれらはすべて $3^0,3^1,\dots ,3^j$ に等しいので、${\Delta }^j{a}_0$ は数列 $c_k=3^k$ の ${\Delta }^j{c}_0$ と同じである。$\Delta c_k=3^{k+1}-3^k=2\cdot 3^k$ より、階差をとるたびに $2$ 倍されて ${\Delta }^j{c}_k=2^j\cdot 3^k$。よって ${\Delta }^j{a}_0=2^j$。

(ii) ${\Delta }^{n+1}{a}_0={\Delta }^{n+2}{a}_0=0$ である。$d$ 次の多項式 $Q(x)$ に対し $Q(x+1)-Q(x)$ は最高次の項が打ち消し合って $d-1$ 次以下になる（定数なら $0$）。$P(x)$ は $n$ 次以下なので、${\Delta }^n{a}_k$ は $k$ によらない定数となり、${\Delta }^{n+1}{a}_k=0$、${\Delta }^{n+2}{a}_k=0$ である。

計算 $(1)$ で $m=n+2$ とすると
$$P(n+2)=\sum _{j=0}^n{}_{n+2}{\mathrm{C}}_j{2}^j.$$
二項定理より $\sum _{j=0}^{n+2}{}_{n+2}{\mathrm{C}}_j{2}^j=(1+2{)}^{n+2}=3^{n+2}$ だから、$j=n+1,n+2$ の項を引いて
$$P(n+2)=3^{n+2}-{}_{n+2}{\mathrm{C}}_{n+1}{2}^{n+1}-2^{n+2}=3^{n+2}-(n+2)\cdot 2^{n+1}-2\cdot 2^{n+1}=3^{n+2}-(n+4)\cdot 2^{n+1}.$$

確認 $n=1$ のとき $P(x)=1+2x$ で $P(3)=7$、式は $27-5\cdot 4=7$。$n=2$ のとき $P(0)=1,P(1)=3,P(2)=9$ から $P(x)=2x^2+1$、$P(4)=33$、式は $81-6\cdot 8=33$。一致する。

よって $P(n+2)=3^{n+2}-(n+4)\cdot 2^{n+1}$。

$e(m)=P(m)-3^m$ とおく。$e(0)=\cdots =e(n)=0$。
$P$ は $n$ 次以下なので、$(n+1)$ 階の階差は $0$：任意の $t$ について ${\sum }_{j=0}^{n+1}(-1{)}^{n+1-j}{}_{n+1}{\mathrm{C}}_{j}P(t+j)=0$。
一方 $3^m$ については ${\sum }_{j=0}^{n+1}(-1{)}^{n+1-j}{}_{n+1}{\mathrm{C}}_j{3}^{t+j}=3^t(3-1{)}^{n+1}=3^t\cdot 2^{n+1}$。

$t=0$: $P(m)=3^m+e(m)$ より $0=2^{n+1}+{\sum }_j(-1{)}^{n+1-j}{}_{n+1}{\mathrm{C}}_{j}e(j)=2^{n+1}+e(n+1)$。よって $e(n+1)=-2^{n+1}$、すなわち $P(n+1)=3^{n+1}-2^{n+1}$。

$t=1$: $0=3\cdot 2^{n+1}+{\sum }_{j=0}^{n+1}(-1{)}^{n+1-j}{}_{n+1}{\mathrm{C}}_{j}e(1+j)$。$e(1+j)$ は $j=n$ と $j=n+1$ 以外で $0$ なので和は $-(n+1)e(n+1)+e(n+2)$。したがって
$$e(n+2)=(n+1)e(n+1)-3\cdot 2^{n+1}=-(n+1)2^{n+1}-3\cdot 2^{n+1}=-(n+4)2^{n+1}.$$
ゆえに
$$P(n+2)=3^{n+2}-(n+4)2^{n+1}.$$

検算: $n=1$ のとき $P(x)=2x+1$（$P(0)=1,P(1)=3$）、$P(3)=7$。公式は $27-5\cdot 4=7$ で一致。$n=2$ のとき $P(0)=1,P(1)=3,P(2)=9$ から $P(x)=x^2+x+1$、$P(4)=21$。公式は $81-6\cdot 8=33$ ... ではなく $n=2$ では $P(n+2)=P(4)$ で、$P(x)=3x^2/2\cdot$ ではなく正しくは $P(x)=2x^2-0x+1$ ではない点を確認する。$P(x)=a{x}^2+bx+1$ とおくと $a+b=2$, $4a+2b=8$ より $a=2,b=0$、$P(x)=2x^2+1$ で $P(4)=33$。公式の $33$ と一致する。