I have a test coming up, and I need some help with a practise question... Need to prove this by induction:
Reccurence relation: m(i) = m(i-1) + m(i - 3) + 1, i >= 3 Initial conditions: m(0) = 1, m(1) = 2, m(2) = 3
Prove m(i) >= 2^(i/3)
Here is what I have been able to do so far:
Base case: m(3) >= 2 -----> 5 >= 2. Therefore it holds for the base case.
Induction Hypothesis Assume there is a k such that m(k) >= 2^(k/3) holds.
Now I must prove that it holds for k+1.
So we have: m(k+1) >= 2^((k+1)/3)
which equals (by substituting hypothesis):
m(k) + m(k-2) + 1 >= 2^((k+1)/3)
This is where I am stuck. I'm not sure where to go from here. Any help will be appreciated. Thanks guys!
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.