Need help with some induction. Please help?

Question

Got 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, for all i >= 3
Initial conditions: m(0) = 1, m(1) = 2, m(2) = 3

Prove m(i) >= 2^(i/3)

(note: m(i) means i is subscript to m)

Here is what I have 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!

Fred · Accepted Answer

In this example, you'll actually have to take i = 0, 1, and 2, all as base cases, because the recursion doesn't produce an m(i) until i = 3. And finite induction (mathematical induction) in its minimal form requires only that, to prove proposition Q(j), for all counting numbers, j, you need to establish:
Q(1...k) for some k≥1,
and then, by assuming Q(1)...Q(n), prove Q(n+1).

i=0: m(0) = 1 = 2^(0/3)
i=1: m(1) = 2 = 2^1 > 2^(1/3)
i=2: m(2) = 3 > 2^1 > 2^(2/3)

Then use the recursion:
m(n+1) = m(n) + m(n-2) + 1
≥ 2^(n/3) + 2^([n-2]/3) + 1
> 2^(n/3) [1 + 2^(-2/3)]

Now at this stage, you need to show that this is ≥ 2^([n+1]/3) = 2^(1/3)*2^(n/3). So if you can show that
1 + 2^(-2/3) ≥? 2^(1/3),
then you're done. Multiply both sides by 2^(2/3):
2^(2/3) + 1 ≥? 2
2^(2/3) ≥? 1 --- Yes!

QED

Trending News

Need help with some induction. Please help?

1 Answer