Prove Inequality By Induction

N

Nazariy

Junior Member
Joined
Jan 21, 2014
Messages
124
Hi,

I need some help on moving this along...

This needs to be proven \(\displaystyle 3^n > n^3 \) for \(\displaystyle n \geq 4 \) using induction

1) Base case: \(\displaystyle 3^4 > 4^3 \)
2) Assume true for n=k; \(\displaystyle 3^k > k^3 \)

And I have no clue what to do next...

\(\displaystyle 3^{k+1} > (k+1)^3 \), I suppose this is the result that I am meant to arrive at, by manipulating \(\displaystyle 3^k > k^3 \)?

i just noticed that there is a hint.. \(\displaystyle 3k^3 - (k+1)^3 = (k-1)^3 + k(k^2 - 6) \)
 
Last edited:
Hint: \(\displaystyle (k-1)^3+k(k^2-6)\ >\ 0\): true or false?
 
Nazariy said:
This needs to be proven \(\displaystyle 3^n > n^3 \) for \(\displaystyle n \geq 4 \) using induction

1) Base case: \(\displaystyle 3^4 > 4^3 \)
2) Assume true for n=k; \(\displaystyle 3^k > k^3 \)

And I have no clue what to do next...
Click to expand...
In general, one works separately with each of the intended results (that is, with each side of the intended formula) to end up with that result. But the precise steps can be non-obvious. Sometimes you just kinda have to fiddle with things until you figure out your way forward. Sometimes you find that way forward by working your way backwards.

Nazariy said:
\(\displaystyle 3^{k+1} > (k+1)^3 \), I suppose this is the result that I am meant to arrive at, by manipulating \(\displaystyle 3^k > k^3 \)?
Click to expand...
Sort of. You probably need to use the "n = k" step, but not as your starting point; you'll probably be plugging it in, somehow, somewhere later in your working.

Nazariy said:
i just noticed that there is a hint.. \(\displaystyle 3k^3 - (k+1)^3 = (k-1)^3 + k(k^2 - 6) \)
Click to expand...
So what have you done with this? What different approaches have you tried?

You need to figure out some way to show that this is true:

. . . . .\(\displaystyle 3^{k+1}\, >\, (k\, +\, 1)^3\)

What happens when we expand the left-hand side?

. . . . .\(\displaystyle 3^{k+1}\, =\, (3^k)(3^1)\, =\, 3(3^k)\)

Hmm... I'm not sure what we can do with this. But we have managed to convert the left-hand side to something that matches the first term in the left-hand side of the "hint". Maybe the hint is wanting us to try to prove the equivalent statement:

. . . . .\(\displaystyle 3^n\, -\, n^3\, >\, 0\)

So let's try reformatting:

. . . . .\(\displaystyle 3^{k+1}\, -\, (k\, +\,1)^3\, =\, 3(3^k)\, -\, (k\, +\, 1)^3\, =\, (k\, -\, 1)^3\, +\, k(k^2\, -\, 6)\)

Now all we have to do is show that the right-hand side is greater than zero.

Hint: Use the fact that k > 3. ;)
 
stapel said:
. . . . .\(\displaystyle 3^{k+1}\, =\, (3^k)(3^1)\, =\, 3(3^k)\)

Hmm... I'm not sure what we can do with this. But we have managed to convert the left-hand side to something that matches the first term in the left-hand side of the "hint". Maybe the hint is wanting us to try to prove the equivalent statement:
Click to expand...

But \(\displaystyle 3(3^k) \neq 3(k^3) \) :)
 
Nazariy said:
But \(\displaystyle 3(3^k) \neq 3(k^3) \) :)
Click to expand...
Did somebody say otherwise?

Try using the almost-completed proof provided earlier, using the hint at the end of the displayed steps. ;)
 
stapel said:
Did somebody say otherwise?
Click to expand...

Since there are only two of us and I did not say otherwise, it follows that it might have been you, but since you did not say so explicitly as well, the answer is: no one said otherwise (until that very moment when I said it) :)

But..

stapel said:
So let's try reformatting:

. . . . .\(\displaystyle 3^{k+1}\, -\, (k\, +\,1)^3\, =\, 3(3^k)\, -\, (k\, +\, 1)^3\, =\, (k\, -\, 1)^3\, +\, k(k^2\, -\, 6)\)

Now all we have to do is show that the right-hand side is greater than zero.

Hint: Use the fact that k > 3. :wink:
Click to expand...


Isn't this implying it implicitly? This part \(\displaystyle ... =\, 3(3^k)\, -\, (k\, +\, 1)^3\, =\, (k\, -\, 1)^3\, +\, k(k^2\, -\, 6)\)

The hint is the following: \(\displaystyle 3k^3 - (k+1)^3 = (k-1)^3 + k(k^2 - 6) \)

And since \(\displaystyle 3k^3 -(k+1)^3 \neq \, 3(3^k)\, -\, (k\, +\, 1)^3\), it must follow that \(\displaystyle \, 3(3^k)\, -\, (k\, +\, 1)^3\, \neq (k\, -\, 1)^3\, +\, k(k^2\, -\, 6)\)

no? :)
 
Nazariy said:
Hi,

I need some help on moving this along...

This needs to be proven \(\displaystyle 3^n > n^3 \) for \(\displaystyle n \geq 4 \) using induction

1) Base case: \(\displaystyle 3^4 > 4^3 \)
2) Assume true for n=k; \(\displaystyle 3^k > k^3 \)

And I have no clue what to do next...

\(\displaystyle 3^{k+1} > (k+1)^3 \), I suppose this is the result that I am meant to arrive at, by manipulating \(\displaystyle 3^k > k^3 \)?

i just noticed that there is a hint.. \(\displaystyle 3k^3 - (k+1)^3 = (k-1)^3 + k(k^2 - 6) \)
Click to expand...

For n>3, try a
(n+1)3 = (n3) + (3n2) + (3n+1) < (n3) + (n3) + (n3) = 3 n3
 
Ishuda said:
For n>3, try a
(n+1)3 = (n3) + (3n2) + (3n+1) < (n3) + (n3) + (n3) = 3 n3
Click to expand...

ahhhhhhhhh :)

Now we have

\(\displaystyle 3n^3 > (n+1)^3 \ \ \textit{(i)}\) and we need to show \(\displaystyle 3(3^n)>(n+1)^3\)

(i) rewritten: \(\displaystyle (n-1)^3 + n(n^2-6) > 0 \ \ \textit{(ii)}\)

\(\displaystyle 3n^3 > 3^{n+1} \) for \(\displaystyle n \geq 4 \), therefore if we prove that (i) is greater than zero we have proved the inequality by induction.

Now I don't see how rewriting (i) as (ii) helps, because in both cases if u plug in values of n starting from 1, you will see that inequalities will be satisfied as soon as you hit 3, so they are true for \(\displaystyle n \geq 3\).. which is not what we want. I suppose this occurs precisely because \(\displaystyle 3n^3 > 3^{n+1}\), i.e. you need a smaller n to satisfy the inequality in the first case (\(\displaystyle 3n^3 > (n+1)^3 \)) than in the latter (\(\displaystyle 3^{n+1}> (n+1)^3\)).

And once again I'm stuck :???:
 
Last edited:
Nazariy said:
ahhhhhhhhh :)

Now we have

\(\displaystyle 3n^3 > (n+1)^3 \ \ \textit{(i)}\) and we need to show \(\displaystyle 3(3^n)>(n+1)^3\)

(i) rewritten: \(\displaystyle (n-1)^3 + n(n^2-6) > 0 \ \ \textit{(ii)}\)

\(\displaystyle 3n^3 > 3^{n+1} \) for \(\displaystyle n \geq 4 \), therefore if we prove that (i) is greater than zero we have proved the inequality by induction.

Now I don't see how rewriting (i) as (ii) helps, because in both cases if u plug in values of n starting from 1, you will see that inequalities will be satisfied as soon as you hit 3, so they are true for \(\displaystyle n \geq 3\).. which is not what we want. I suppose this occurs precisely because \(\displaystyle 3n^3 > 3^{n+1}\), i.e. you need a smaller n to satisfy the inequality in the first case (\(\displaystyle 3n^3 > (n+1)^3 \)) than in the latter (\(\displaystyle 3^{n+1}> (n+1)^3\)).


And once again I'm stuck :???:
Click to expand...
We have \(\displaystyle 3n^3 > (n+1)^3\). By the induction assumption \(\displaystyle 3^n \gt n^3\) so that \(\displaystyle 3^{n+1} = 3 (3^n) > 3 (n^3) > (n+1)^3\)
 
Ishuda said:
\(\displaystyle 3^{n+1} = 3 (3^n) > 3 (n^3) > (n+1)^3\)
Click to expand...

is it not \(\displaystyle 3(n^3)> 3 (3^n) > (n+1)^3\) ?

please answer whether this is correct?

well it looks like we have proved the inequality by induction?
 
Nazariy said:
is it not \(\displaystyle 3(n^3)> 3 (3^n) > (n+1)^3\) ?

please answer whether this is correct?

well it looks like we have proved the inequality by induction?
Click to expand...

Is 3 (43) = 192 greater than 3(34)= 243? Look at the original question.
 
Ishuda said:
It's there in bits and pieces. I think it needs to be put together.
Click to expand...

Hmmm.. It does not add up

1) Base case: \(\displaystyle n = 4, 3^4 > 4^3, 81>64 \)
2) Assume true for n=k, so: \(\displaystyle 3^k > k^3 \) for \(\displaystyle k \geq 4 \)
3) Prove that \(\displaystyle 3 ^ {k+1} > (k+1)^3 \)

Consider \(\displaystyle (k+1)^3\), \(\displaystyle (k+1)^3=k^3+3k^2+(3k+1) < k^3 + k^3 + k^3 \), i.e. \(\displaystyle (k+1)^3 < 3k^3 \)
Now this inequality is true for \(\displaystyle k \geq 3 \)

Since \(\displaystyle 3(3^k) \geq 3(k^3) \) for all \(\displaystyle k \geq 1 \) we have \(\displaystyle 3(3^k) > 3(k^3) > (k+1)^3 \)

hmmm... and we have not used the fact that k is greater or equal to 4 anywhere :confused:
 
Nazariy said:
Hmmm.. It does not add up

1) Base case: \(\displaystyle n = 4, 3^4 > 4^3, 81>64 \)
2) Assume true for n=k, so: \(\displaystyle 3^k > k^3 \) for \(\displaystyle k \geq 4 \)
3) Prove that \(\displaystyle 3 ^ {k+1} > (k+1)^3 \)

Consider \(\displaystyle (k+1)^3\), \(\displaystyle (k+1)^3=k^3+3k^2+(3k+1) < k^3 + k^3 + k^3 \), i.e. \(\displaystyle (k+1)^3 < 3k^3 \)
Now this inequality is true for \(\displaystyle k \geq 3 \)

Since \(\displaystyle 3(3^k) \geq 3(k^3) \) for all \(\displaystyle k \geq 1 \) we have \(\displaystyle 3(3^k) > 3(k^3) > (k+1)^3 \)

hmmm... and we have not used the fact that k is greater or equal to 4 anywhere :confused:
Click to expand...

Is (3k+1) < k3 for all k? Nope, just for k>1. Is 3k2 < k3 for all k? Nope, just for k ???
 
Ishuda said:
Is (3k+1) < k3 for all k? Nope, just for k>1. Is 3k2 < k3 for all k? Nope, just for k ???
Click to expand...

more than 4, yes. Thank you. I've got a different solution. I will post shortly. For anyone's future reference.
 
\(\displaystyle
\begin{align*}
(k + 1)^3
&= k^3 + 3k^2 + 3k + 1 \\
&< k^3 + 3k^2 + 3k + (k) &\text{since } k \geq 4 > 1 \\
&= k^3 + 3k^2 + 4k \\
&\leq k^3 + 3k^2 + (k)k &\text{since } k \geq 4 \\
&= k^3 + 4k^2 \\
&\leq k^3 + (k)k^2 &\text{since } k \geq 4 \\
&= 2k^3 \\
&< 3k^3 \\
&< 3(3^k) \\
&= 3^{k + 1}
\end{align*}
\)
 
Nazariy said:
Prove 3n > n3 for all n \(\displaystyle \ge\) 4 by induction:
It is true that 34 = 81 > 64 = 43.
Induction assumption; assume it is true for n=k. Then
\begin{align*}
(k + 1)^3
&= k^3 + 3k^2 + 3k + 1 \\
&< k^3 + 3k^2 + 3k + (k) &\text{since } k \geq 4 > 1 \\
&= k^3 + 3k^2 + 4k \\
&\leq k^3 + 3k^2 + (k)k &\text{since } k \geq 4 \\
&= k^3 + 4k^2 \\
&\leq k^3 + (k)k^2 &\text{since } k \geq 4 \\
&= 2k^3 \\
&< 3k^3 \\
&< 3(3^k)\\
&= 3^{k + 1}
\end{align*}

and it is true for n=k+1. So, by induction, it is true for all n \(\displaystyle \ge\) 4
Click to expand...

To be a little more formal, see above. You should probably also add "by the induction assumption" to the <3(3k) line also
 
You must log in or register to reply here.
Top