2019ISL-A5 (便乗)

とりあさんが面白い解法を紹介していたので( これ )私は普通の解法を紹介します.

対称的な恒等式なので帰納法かラグランジュ補完を使えば出来そうだと思いました. なのでとりあえずラグランジュ補完の式を書いてみると...($f$を高々$n-1$次の多項式として)
$$f(x)=\sum_{i=1}^n f(x_i)\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}$$
なんかどうやっても完全に同じ式にすることは出来なさそう...(ちなみに公式解答にあるよう, 一部の係数のみ取り出すなど上手くやればこの方針でも出来ますが私は諦めました.)

すると帰納法が考えられます. ひとまずこの方針で考えていきます.
帰納法のステップを考えやすくするためにまずは示すべき式の左辺を$F(x_1,...,x_n)$とします. $n=1$のときは空積は$1$なので$F(x_1)=1$. $n=2$のときは$F(x_1,x_2)=\dfrac{1-x_1x_2}{x_1-x_2}+\dfrac{1-x_1x_2}{x_2-x_1}=0$ なのでやはり問題ないですね.
次は帰納法のステップを作れるか考えてみます. このために「$n=k$の時が正しいならば$n=k+1$の時も正しい」を示さないと行けないわけですが, 十分条件的なノリで「$n=k+1$の時正しいならば$n=k$の時も正しい」が言えるかを考えてみました. (これが上手くいかないと$n=k$の時と$n=k+1$の時の関係を見いだすのが難しいことになり, 少し帰納法の方針は渋そうという気分になるので) まあやれることは少なくて特殊値を代入して$F(x_1,x_2,...,x_{k+1})$から$F(x_1,...,x_k)$の形を作るぐらいしかありません. そこで式がきれいになりそうな値を探すと$x_{k+1}=1$のとき$F(x_1,...,x_k,1)=1-F(x_1,...,x_k)$となることがわかります. なのでもう少し帰納法の方針を粘って探してみます. 帰納法の仮定からいくつかの特殊値を求めてそこから上手い具合に($n$次関数は$n+1$個の点が分かれば一意に定まる的な定理を使って)示せないか, という感じです.

ここでこの問題を思い出してみましょう.

この問題は平行移動して式を簡単にして帰納法を回すのです.
と言うわけで差の部分が共通しているので平行移動が上手くいかないかと考えます.$F(x_1-a,x_2-a,...,x_n-a)$を計算すると,
$$F(x_1-a,x_2-a,...,x_n-a)=\sum_{1 \le i \le n} \prod_{j \neq i} \frac{1-(x_{i}-a)(x_{j}-a)}{x_{i}-x_{j}}$$
となります, この右辺は$a$に関する高々$2n-2$次関数です. ここで方針を再確認します.

そこで式がきれいになりそうな値を探すと$x_{k+1}=1$のとき$F(x_1,...,x_k,1)=1-F(x_1,...,x_k)$となることがわかります. なのでもう少し帰納法の方針を粘って探してみます. 帰納法の仮定からいくつかの特殊値を求めてそこから上手い具合に($n$次関数は$n+1$個の点が分かれば一意に定まる的な定理を使って)示せないか, という感じです.

すると$a=x_i-1$のとき左辺に帰納法の仮定が使えそうです. これによって($x_i$達は相異なるので)$n$個の特殊値が分かりました. あと$n-1$個特殊値が求まればよいですね. そこで似たような代入を探すと($-1$で上手くいくなら$+1$も試すかというノリでやったのですが)$a=x_i+1$のときも上手く約分されて帰納法の仮定が適用できることが分かります. よって$a$の特殊値が$2n$個求まってめでたしめでたし...

と言いたいところですが$x_i-1=x_j+1$が成立しているとこの議論は回りません. 従って$x_i$達が十分離れていることを仮定してその後に一致の定理みたいな議論で任意の$x_i$で恒等式になっていることを言ってあげればよいでしょう.
これでこの問題を完全に解くことが出来ました.

感想
帰納法はすごい