Need help with simple induction proof... 10 pts!?

We will prove the stronger result, P(n), that m_n ≥ 3^(n/3), for all n ≥ 0.

Base case:

P(0) is true, since 1 ≥ 3^0 = 1.

P(1) is true, since 2 ≥ 3^(1/3), since 2³ ≥ 3.

P(2) is true, since 3 ≥ 3^(2/3).

Note that 3^(2/3) > 2 <=> 3² > 2³. We will need this result below.

Now we show that, for n > 2, P(n-3) and P(n-1) together imply P(n).

m_n = m_(n-1) + m_(n-3) + 1 ≥ 3^((n-1)/3) + 3^((n-3)/3) + 1, by the induction hypothesis.

= 3^((n-3)/3) (3^(2/3) + 1) + 1

> 3^(n/3) + 1, since 3^(2/3) > 2.

Hence, by mathematical induction, P(n) is true for all n ≥ 0.

Thus m_i ≥ 3^(i/3) ≥ 2^(i/3), for all i ≥ 0.

(This is a form of strong induction, sometimes called complete induction; see the first link below.)

Table of value for n, m_n, 3^(n/3), 2^(n/3), for n = 0, 1, ... 10:

0, 1, 1.0, 1.0

1, 2, 1.44224957031, 1.25992104989

2, 3, 2.08008382305, 1.58740105197

3, 5, 3.0, 2.0

4, 8, 4.32674871092, 2.51984209979

5, 12, 6.24025146916, 3.17480210394

6, 18, 9.0, 4.0

7, 27, 12.9802461328, 5.03968419958

8, 40, 18.7207544075, 6.34960420787

9, 59, 27.0, 8.0

10, 87, 38.9407383983, 10.0793683992

11, 128, 56.1622632224, 12.6992084157

12, 188, 81.0, 16.0

13, 276, 116.822215195, 20.1587367983

14, 405, 168.486789667, 25.3984168315

15, 594, 243.0, 32.0

16, 871, 350.466645585, 40.3174735966

17, 1277, 505.460369002, 50.796833663

18, 1872, 729.0, 64.0

19, 2744, 1051.39993675, 80.6349471933

20, 4022, 1516.381107, 101.593667326

we are able to coach by employing mathematical induction: First we practice that fact is actual for n = a million a million^3 - a million = 0 Now we practice that if fact is actual for n = ok-a million, then it is likewise actual for n = ok actual for n = ok-a million: (ok-a million)^3 - (ok-a million) is divisible by employing 6 (ok-a million)^3 - (ok-a million) = ok^3 - 3k^2 + 3k - a million - ok + a million = ok^3 - ok - 3k^2 + 3k = ok^3 - ok - 3k(ok - a million) ok^3 - ok = (ok-a million)^3 - (ok-a million) + 3k(ok - a million) Now (ok-a million)^3 - (ok-a million) is divisible by employing 6 and 3k(ok - a million) is divisible by employing the two 3 and a pair of (considering one in all ok or ok-a million is even) ok^3 - ok is sum of two numbers divisible by employing 6 consequently ok^3 - ok is divisible by employing 6 So, by employing mathematical induction, fact is actual for all n >= a million