方針
初期値を ,漸化式を として扱う。固定点は なので,誤差 を導入する。漸化式から が得られ, より分母が と の間にあることを使って上下から評価する。最大の は,誤差比が に近づくことから決める。
解答
初期値を とし, として考える。
(1)
まず と単調増加を示す。 であり, なら である。よって帰納法により がすべての で成り立つ。
また のとき, は と同値である。両辺は非負なので二乗してよく, すなわち である。これは から成り立つ。したがって である。
次に下からの評価を示す。 とおくとここで だから であり, である。また なので,帰納法により である。すなわち であり, である。
以上より が成り立つ。
(2)
(1) と同じく とおく。上で得た式 を用いる。 だから であり, である。また である。したがって帰納法により である。すなわち である。
(3)
(2) より は条件を満たす。
これより大きい が条件を満たさないことを示す。 は増加して2より小さいので,極限を とすると である。 より である。したがって である。
いま とする。 となる を1つ取る。十分大きい では が成り立つ。するとある番号 以後で となる。ところが なので,十分大きい では となる。したがって となる が存在し,すべての について 、すなわち を満たすことはできない。
よって最大の定数は である。
固定点2へ近づく反復
階段状の線は の反復を表し、固定点2へ近づく。
総評
難度は10段階中7、計算量は10段階中6。目安時間は30分程度で、固定点 との差 を見ることが決定的である。単調増加と上界を先に示しておくと、分母 を と で挟む評価が使える。(3) は単に (2) の結果を読むだけではなく、誤差比が に近づくため,それより大きい はいずれ破綻することを示す必要がある。添字は から始まる形で整理すると不等式が自然にそろう。