Discrete Mathematics Problem?

Question

Hello,

I have a mathematical induction problem I need some assistance on.

Here's the problem:

Prove by induction on n that, n^3 (less than or equal to) 2^n for n (greater than or equal to) 10 a positive integer.

So far, I can only get part of the problem (if I am correct to that point?) then I get stuck. Here is what I have:

First let n = k then I have k^3 (less than or equal to) 2^k
Then substitue n = k + 1 so I get (k + 1)^3 (less than or equal to) 2^(k + 1)

From here I get stuck. Any help would be greatly appreciated. Thanks in advance!

**********************************************

Thank you Pascal and rhsaunder...

Pascal. I am being taught to solve these proofs very similar to the way you solved the problem. I need some clarification if I can.

Here is what I have so far.

P(n): n^3 <= 2^n for n>=10 a positive integer.

Step 1: Let n=10 so I get 10^3 <= 2^10 which is 1000<=1024

Step 2: Assume P(k) is true for n=k
So, k^3<=2^k (Ind. Hyp.)

Step 3: Must show P(k+1) is true. Let n=k+1
So, (k+1)^3<=2^(k+1)
We know k^3<=2^k
From here 2k^3<=2^k*2
Which is 2k^3<=2^(k+1)

Then:
(k+1)^3 = K^3+3k^2+3k+1=K^3+(9K^2+9k+3)/3

From here I get lost when I introduce n>=10.

Need clarification on this Pascal - Since n≥10, 9n² < n*n²=n³, and likewise 9n < n³ and 3 < n < n³.

Thank you again!
***********************************************************************

Answer 1

Suppose n³<2^n and n≥10

(n+1)³ = n³+3n²+3n+1
n³+3n²+3n+1 = n³ + (9n²+9n+3)/3

Since n≥10, 9n² < n*n²=n³, and likewise 9n < n³ and 3 < n < n³. So:

n³ + (9n²+9n+3)/3 < n³ + (n³+n³+n³)/3
n³ + (n³+n³+n³)/3 = n³+n³ = 2n³

By our inductive hypothesis, n³<2^n, so:

2n³ < 2*2^n = 2^(n+1)

From these inequalities, by transitivity we have

(n+1)³ < 2^(n+1)

So now all that remains is to establish the base case

10^3 = 1000 < 1024 = 2^10

Thus, n³<2^n if n=10, and n≥10 ∧ n³ < 2^n → (n+1)³ < 2^(n+1), so by induction we have that n³ < 2^n for all n≥10. Q.E.D.

Edit: sorry for not replying to your inquiry earlier, unfortunately I was being kept busy at school. These inequalities come from the fact that n is greater than or equal to 10. So 99, n is certainly greater than 1, so we obtain that n³>n². Combining this with the previous we have n³>n²>9n, giving us n³>9n. Finally, than n³>3 follows directly from the fact that n>3 (if you want a formal proof, consider the sequence n>1, n²>n (multiplying both sides by n), n³>n² (previously shown), and by transitivity, n³>n²>n>3, so n>3. But it really should be obvious).

The key to what we're doing is that we are massively overestimating each term in order to get the expression into a nice form that we can easily compare to 2^(n+1). The reason for choosing those particular inequalities was simply that it made the underlying expressions easier to work with. Sometimes this meant employing inequalities which were in fact much weaker than the ones we started with (i.e. using that n≥10 to prove that n³>3). But by replacing each term with one we knew to be greater, and then showing that this overestimate of (n+1)³ was less than 2^(n+1), we were able to show that (n+1)³<2^(n+1) as well.

By the way, since I've had time to think about it, I've come up with a slightly more elegant proof of the inductive step, that uses only one overestimate. Here it is:

n≥10, so n(∛2-1)>1 (in fact, it would suffice for n to be greater than or equal to 4, which n≥10 certainly is). It follows then (by adding n to both sides) that n∛2>n+1, and since the cube function is monotone (meaning that a>b → a³>b³), this means that we can cube both sides to obtain 2n³>(n+1)³. Of course, 2n³<2*2^n=2^(n+1) by the inductive hypothesis, so by transitivity it follows that (n+1)³<2^(n+1), as required.

Answer 2

The usual drill for these is to find a case for which the claim is true, and show that it is true for each larger case. So, let's try it for n = 10 and see what happens.
n^3 <= 2^n ? 1000 <= 1024. Check. Add one:
1331 <= 2048? Check again. Furthermore, the difference has increased, so we can see that the claim is true. But it is not yet a proof. So, let's change direction, and try log of both sides. 3 log n <= n log 2 ? Bingo! log n will be less than n, and although 3 is not less than log 2, we can (and already have) find an n for which the claim is true, and since log n is less than n for that number and all larger ones, we've got it.