Since m(k+1) = m(k) + m(k-2) + 1, you can replace = with >= to get m(k+1) >= m(k) + m(k-2) + 1.
You can make substitutions on the right-hand side of >=, as long as what you put in is less than or equal to what you take out. Start by using #1 to make a substitution in #2.
Consider your base case: you show that for 3 prior consecutive given values for m(0), m(1), and m(2), that the formula holds for m(4). Then show that m(k+1) formula works if you assume that it's true for 3 prior values m(k), m(k-1), and m(k-2) [this is valid for induction].
By initial condition
m(k+1) = m(k) + m(k-2) + 1
Substitution:
m(k+1) >= 2^(k/3) + 2^((k-2)/3) + 1
Factor the right hand side in terms of 2^((k+1)/3) [HINT: leave the +1 alone] and it should fall out from there.
发布评论
评论（2）
提示：
证明 m(k) >= m(k-2)。 （这很简单。）
由于 m(k+1) = m(k) + m(k-2) + 1，因此您可以将
=替换为>=< /code> 得到 m(k+1) >= m(k) + m(k-2) + 1。你可以只要您输入的内容小于或等于您取出的内容，就可以在
>=的右侧进行替换。首先使用 #1 替换 #2。Hints:
Prove that m(k) >= m(k-2). (This is trivial.)
Since m(k+1) = m(k) + m(k-2) + 1, you can replace
=with>=to get m(k+1) >= m(k) + m(k-2) + 1.You can make substitutions on the right-hand side of
>=, as long as what you put in is less than or equal to what you take out. Start by using #1 to make a substitution in #2.考虑您的基本情况：您表明，对于 m(0)、m(1) 和 m(2) 的 3 个先前连续给定值，该公式适用于 m(4)。然后证明，如果您假设 3 个先验值 m(k)、m(k-1) 和 m(k-2) 都成立，则 m(k+1) 公式有效[这对归纳有效]。
根据初始条件
替换：
将右侧分解为 2^((k+1)/3) [提示：保留 +1]，它应该从那里消失。
Consider your base case: you show that for 3 prior consecutive given values for m(0), m(1), and m(2), that the formula holds for m(4). Then show that m(k+1) formula works if you assume that it's true for 3 prior values m(k), m(k-1), and m(k-2) [this is valid for induction].
By initial condition
Substitution:
Factor the right hand side in terms of 2^((k+1)/3) [HINT: leave the +1 alone] and it should fall out from there.