OMCE002(C) - ラグランジュの補間公式

　自分は公式解説のような初手に至らなかったので，以下のように解きました．その解法を（備忘録も兼ねて）まとめておこうと思います．まずは，ラグランジュの補間公式についての紹介です．

ラグランジュの補間公式． $N+1$ 個の点 $(x_0, y_0), (x_1, y_1), \ldots (x_N, y_N)$ （$x_0\lt x_1 \lt \cdots \lt x_N$ としておく）がある．これらすべてを通る $N$ 次以下の多項式 $f(x)$ は，以下のように表される： $$f(x) = \sum_{n=0}^{N} y_n \dfrac{g_n(x)}{g_n(x_n)}.$$ ただし，$g_n(x)=\displaystyle \prod_{k\neq n} (x-x_k)$ である．

　はじめてこの式を見たという方は，中学・高校数学の問題集にも載っているような「指定された $2\ (3)$ 点をすべて通るような直線（放物線）の式を求めよ 」という問題を例にしてこの式を書き下してみると，「これが何をやっているものなのか」について感覚を掴めるかと思います！
　早速，今回の問題にラグランジュ補間を適用してみましょう．

今回の場合 $N=10000, x_n=n, y_n =(n+1) 2^n$ とすればよさそうである．まずは $g_n(x_n)$ を求める．

$$\begin{aligned} g_n(x_n)=g_n (n) &= (n-0)(n-1) \cdots 1\cdot (-1)(-2) \cdots (n-N)\\ &= n!\ (N-n)!\ (-1)^{N-n}. \end{aligned}$$

今回求めるのは，$f(N+1)$ であるから，$g_n(N+1)$ も求めておく．

$$g_n(N+1) = \displaystyle \prod_{k\neq n} (N+1-k) = \dfrac{(N+1)!}{N+1-n}.$$

ここで，ラグランジュの補間公式を適用すると

$$\begin{aligned} f(N+1) &= \sum_{n=0}^{N} (n+1) 2^n \dfrac{(N+1)!}{N+1-n} \cdot \dfrac{1}{ n!\ (N-n)!\ (-1)^{N-n}}\\ &= \sum_{n=0}^{N} (n+1) \dfrac{(N+1)!}{(N-n+1)\ (N-n)!\ n!} 2^n (-1)^{N-n}\\ &= \sum_{n=0}^{N} (n+1)\ {}_{N+1} \mathrm{C} _{n}\ 2^n (-1)^{N-n}\\ &= \underbrace{\sum_{n=0}^{N} {}_{N+1} \mathrm{C} _{n}\ 2^n (-1)^{N-n}}_{=A} + \underbrace{\sum_{n=0}^{N} n\ {}_{N+1} \mathrm{C} _{n}\ 2^n (-1)^{N-n}}_{=B} \end{aligned}$$ と変形できる．$A,B$ それぞれについて，次のように計算できる．

$$\begin{aligned} A &= -\sum_{n=0}^{N} {}_{N+1} \mathrm{C} _{n}\ 2^n (-1)^{N+1-n} \\ &= -\Biggl(\sum_{n=0}^{N+1} {}_{N+1} \mathrm{C} _{n}\ 2^n (-1)^{N+1-n} - {}_{N+1} \mathrm{C} _{N+1}\ 2^{N+1} (-1)^{N+1-(N+1)} \Biggl)\\ &= -\Bigl( \bigl(2+(-1)\bigl)^{N+1} - 2^{N+1} \Bigl)\\ &= 2^{N+1}-1. \end{aligned}$$

$$\begin{aligned} B&= \sum_{n=0}^{N} n\ \dfrac{(N+1)!}{n\ (n-1)!\ (N+1-n)!}\ 2^n (-1)^{N-n}\\ &= (N+1) \sum_{n=1}^{N} \ \dfrac{N!}{(n-1)!\ (N+1-n)!}\ 2^n (-1)^{N-n}\\ &= (N+1) \sum_{n=1}^{N} {}_{N} \mathrm{C} _{n-1}\ 2^n (-1)^{N-n}\\ &= -2(N+1) \sum_{n=1}^{N} {}_{N} \mathrm{C} _{n-1}\ 2^{n-1} (-1)^{N+1-n}\\ &= -2(N+1) \Biggl( \sum_{n=1}^{N+1} {}_{N} \mathrm{C} _{n-1}\ 2^{n-1} (-1)^{N-n+1} - {}_{N} \mathrm{C} _{N+1-1}\ 2^{N+1-1} (-1)^{N+1-(N+1)} \Biggl)\\ &= -2(N+1) \Bigl( \bigl(2+(-1)\bigl)^{N} -2^N \Bigl)\\ &= -2(N+1)+(N+1)\ 2^{N+1}. \end{aligned}$$

以上より $$\begin{aligned} f(N+1) &=2^{N+1}-1 -2(N+1)+(N+1)\ 2^{N+1}\\ &= N\ 2^{N+1} +2^{N+2} -2N-3. \end{aligned}$$ と公式解説にある表示を得ることができた．

　このユーザー解説の執筆にあたり，高校数学の美しい物語さんの記事（https://manabitimes.jp/math/726 ）を参考にさせていただきました．最後に，ラグランジュの補間公式が使えるかもしれないOMCの問題を，自分が記憶している限りでまとめて終わりにします（ネタバレ注意です）．