prove n^3<3^n by mathematical induction for n>=4?

2013-08-25 11:30 am

回答 (4)

2013-08-26 2:33 am
✔ 最佳答案
This base case holds since 4^3 < 3^4.

To show that the inductive step holds, we need to show that:
if (n + 1)^3 < 3^(n + 1) holds, n^3 < 3^n holds.

Note that:
3^(n + 1) = 3 * 3^n
> 3n^3, since 3^n > n^3 by the inductive hypothesis
> (n + 1)^3. (see below)

Then, since we have shown that 3^(n + 1) > (n + 1)^3 holds if 3^n > n^3 holds and that the base case holds, the proof is complete.

<== Proof of 3n^3 > (n + 1)^3: ==>
By binomial expansion, we have:
(n + 1)^3 = n^3 + 3n^2 + 3n + 1.

So:
3n^3 > (n + 1)^3 ==> 3n^3 > n^3 + 3n^2 + 3n + 1 ==> 2n^3 - 3n^2 - 3n - 1 > 0.

Since 2n^3 - 3n^2 - 3n - 1 = 0 has a real solution on (2, 3) (this is true since f(2) and f(3) have opposite signs) and this is the only positive real solution via Descartes' Rule of Signs, we see that 2n^3 - 3n^2 - 3n - 1 > 0 holds on the interval [4, infinity). Back-tracking from this inequality yields 3n^3 > (n + 1)^3, and so the proof is complete.
<== END PROOF ==>
2013-08-25 6:52 pm
Hi Kanika

The mathematical method of proof by induction has 3 steps you need to go through.

Step 1: Test the parameters given.
If the parameters are false, the assignment is not true.
If parameters are true, continue to step 2

Step 2: Assume that the parameters is true for any random number you can pick within the parameters. For example "k".

Step 3: Test the equation for (k+1) and show that it is still true.
If the equation is false, the assignment is not true.
If the equation is true, you have proven by induction that the equation is true.

The reply from Alice only contains Step 1 of the induction proof method, the testing of what you know, and the statement that the biggest value of n is 4. The assignment is the opposite: all n equal to or larger than 4. You need to continue onto Step 2 and Step 3 for it to be a full proof by induction.

An example:

Proof by induction, that: n^3<3^n for n>=4

Step 1: The test of the value we are given (n is 4 or larger, so we test for n=4)
n^3 < 3^n
4^3 < 3^4
64 < 81 - this statement is true, so we continue onto Step 2

Step 2: The assumption, that n can be any value, and that we can name n to k, as long as k is equal to or larger than 4.
We set n = k and get following inequality =>
k^3 < 3^k , (k>=4)

Step 3: Proving that the inequality still is true when you increase k by 1.
(k+1)^3 < 3^(k+1) , (k>=4)
(k+1)^3 < 3*3^(k)
(k+1)(k+1)(k+1) < 3*3^k
k^3+3k^2+3k+1 < 3^k + 3^k + 3^k
Split the inequality into 3 partial inequalities.
(1) k^3 < 3^k We know this is true from Step 2
(2) 3k^2 < 3^k We know that k>=4, which mean that 3k^2<k^3. Therefore this inequality is true.
(3) 3k+1 < 3^k We know that k>=4, which mean that 3k+1<k^3. Therefore this inequality is true too.
Since each partial inequality above is true, it is given that they combined must be true also.

Thus (k+1)^3 < 3^(k+1) is proven.

And we can say that the original inequality is true for all numbers n >=4.

Hope it helped!
參考: Discrete mathematics
2013-08-25 6:49 pm
n^3<3^n , n>=4
so the biggest amount of n is 4
when n is 4
4^3<3^ 4
L.H.S=4^3
=64
R.H.S=3^4
=81
so 64>81
n^3<3^n
2013-08-25 6:30 pm
dunno


收錄日期: 2021-04-16 16:16:03
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20130825033033AA5WKzU

檢視 Wayback Machine 備份