Proving a recurrence relation by induction [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

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!

Answer 1

Hints:

1. Prove that m(k) >= m(k-2). (This is trivial.)

2. 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.

3. 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.

Answer 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.