Fekete's lemma
一つ前の記事と似てるような似てないような、なので書いておく
を数列とする。任意のに対して
(優加法性) を満たすならば、
を満たす
直感的には、とりあえずが(どこかから)非減少列であることを示せてしまえればよさそうに見える。
しかし、この方針では厳しい。たとえば、
のようにととれば優加法性を満たし、かつ
を大きくとることによって となる。
ということで、別の方針で示す必要がある。証明はCombinatorial Optimization (Schrijver)の2章の証明に説明を少し追加したものである。
とする
優加法性から
を固定して
最後の式はlimを飛ばして(無限大にもなりうるが)収束するのでliminfでも大丈夫。
また、この変形の最後でを含まなかったので次のようにできる
よって、
とできる。
liminfとlimsupの定義から、
なので、先ほどの式とあわせることで、これらには等式が成り立つことがわかる。
結局、liminfとlimsupが一致したので、limが存在することがわかり、