1
$\begingroup$

I am reading through a proof of $4^n > n^4$ for $n \geq 5$ using induction.

For the induction step, $4^{n + 1} > (n + 1)^4$ must be proven, and we know that $4^{n + 1} > 4n^4$ from the induction hypothesis. (All for $n \geq 5$, of course.)

The proof says that it is adequate to show that that $4n^4 \geq (n + 1)^4$ for $n = 5$, but how do we know that $4^{n + 1} > 4n^4 \geq (n + 1)^4$? Can't it be something like $4^{n + 1} > (n + 1)^4 > 4n^4$ since the only fact we know is that $4^{n + 1} > 4n^4$, and this is true for $4^{n + 1} > (n + 1)^4 > 4n^4$ also (or $4^{n + 1} > (n + 1)^4 \geq 4n^4$)?

And why is it $4n^4 \geq (n + 1)^4$ and not $4n^4 > (n + 1)^4$? (Greater than or equal to vs. strictly greater than)

$\endgroup$
3
$\begingroup$

To prove $4n^4 \geq (n+1)^4$, we can prove $$(1 + \frac{1}{n})^4 \leq 4$$ which is true as long as $n \geq 3$, since the LHS in strictly decreasing in $n$

And as you can see, the inequality can of course be made strict.

$\endgroup$
  • $\begingroup$ @nablablah Yes you can write it in the strict way, as I said at the end of my answer $\endgroup$ – Petite Etincelle Oct 6 '14 at 9:11
2
$\begingroup$

$4n^{4}-\left(n+1\right)^{4}=\left(2n^{2}-\left(n+1\right)^{2}\right)\left(2n^{2}+\left(n+1\right)^{2}\right)=\left(n^{2}-2n-1\right)\left(3n^{2}+2n+1\right)$ so it is enough to show that $n^{2}-2n-1\geq0$ for $n\geq5$.

Note that $n^{2}-2n-1=\left(n-1\right)^{2}-2$ showing that it is enough to show that $m^2\geq 2$ for $m\geq4$.

Sure you can take it from here :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.