テストが近づいているので、練習問題の助けが必要です... これを帰納法で証明する必要があります。
再帰関係: m(i) = m(i-1) + m(i - 3) + 1、i >= 3 初期条件: m(0) = 1、m(1) = 2、m(2) = 3
m(i) >= 2^(i/3) を証明する
これまでに私ができることは次のとおりです。
基本ケース: m(3) >= 2 ------> 5 >= 2. したがって、基本ケースが成り立ちます。
帰納仮説m(k) >= 2^(k/3) を満たす ak があるとします。
ここで、k+1 に対して成り立つことを証明しなければなりません。
m(k+1) >= 2^((k+1)/3)
（仮説を代入することにより）等しい：
m(k) + m(k-2) + 1 >= 2^((k+1)/3)
これは私が立ち往生しているところです。ここからどこへ行けばいいのかわからない。どんな助けでも大歓迎です。みんなありがとう！
ヒント：
m(k) >= m(k-2) であることを証明してください。(これは些細なことです。)
m(k+1) = m(k) + m(k-2) + 1 なので、 で置き換える=と>=、m(k+1) >= m(k) + m(k-2) + 1 を得ることができます。
>=入れたものが取り出したもの以下である限り、の右側で置換を行うことができます。#1 を使用して #2 を置換することから始めます。
基本ケースを考えてみましょう: m(0)、m(1)、および m(2) の 3 つの連続する与えられた値に対して、式が m(4) に対して保持されることを示します。次に、m(k)、m(k-1)、および m(k-2) の 3 つの事前値に対して真であると仮定すると、m(k+1) 式が機能することを示します [これは帰納法に有効です]。
初期状態による
m(k+1) = m(k) + m(k-2) + 1
置換:
m(k+1) >= 2^(k/3) + 2^((k-2)/3) + 1
右辺を 2^((k+1)/3) [ヒント: +1 はそのままにしておく] で因数分解すると、そこから外れます。