Prove Inequality By Induction

[Nazariy]

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)$

 

[Limax]

Hint: $\displaystyle (k-1)^3+k(k^2-6)\ >\ 0$: true or false?

 

[Nazariy]

Hint: $\displaystyle (k-1)^3+k(k^2-6)\ >\ 0$: true or false?

True

 

[stapel]

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...

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.

$\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$?

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.

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

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.

 

[Nazariy]

. . . . .$\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:

But $\displaystyle 3(3^k) \neq 3(k^3)$

 

[stapel]

But $\displaystyle 3(3^k) \neq 3(k^3)$

Did somebody say otherwise?

Try using the almost-completed proof provided earlier, using the hint at the end of the displayed steps.

 

[Nazariy]

Did somebody say otherwise?

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..

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:

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?

 

[Ishuda]

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)$

For n>3, try a
(n+1)³ = (n³) + (3n²) + (3n+1) < (n³) + (n³) + (n³) = 3 n³

 

[Nazariy]

For n>3, try a
(n+1)³ = (n³) + (3n²) + (3n+1) < (n³) + (n³) + (n³) = 3 n³

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 :???:

 

[Ishuda]

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 :???:

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$

 

[Nazariy]

$\displaystyle 3^{n+1} = 3 (3^n) > 3 (n^3) > (n+1)^3$

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?

 

[Ishuda]

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?

Is 3 (4³) = 192 greater than 3(3⁴)= 243? Look at the original question.

 

[Nazariy]

Is 3 (4³) = 192 greater than 3(3⁴)= 243? Look at the original question.

i have totally confused myself there.. You are correct. So the proof by induction is complete I suppose

 

[Ishuda]

i have totally confused myself there.. You are correct. So the proof by induction is complete I suppose

It's there in bits and pieces. I think it needs to be put together.

 

[Nazariy]

It's there in bits and pieces. I think it needs to be put together.

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

 

[Ishuda]

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

Is (3k+1) < k³ for all k? Nope, just for k>1. Is 3k² < k³ for all k? Nope, just for k ???

 

[Nazariy]

Is (3k+1) < k³ for all k? Nope, just for k>1. Is 3k² < k³ for all k? Nope, just for k ???

more than 4, yes. Thank you. I've got a different solution. I will post shortly. For anyone's future reference.

 

[Nazariy]

\(\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*}
\)

 

[Ishuda]

Prove 3ⁿ > n³ for all n $\displaystyle \ge$ 4 by induction:
It is true that 3⁴ = 81 > 64 = 4³.
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

To be a little more formal, see above. You should probably also add "by the induction assumption" to the <3(3^k) line also