4
$\begingroup$

One of the practice problems I have is to prove by induction that for every $n \geq 4$ the following inequality holds:

$5^n \geq 5n^3 + 2$

My progress so far (inequality holds for base case $n=4$):

$5^{n+1} \geq 5(5n^3 + 2)$

$5^{n+1} \geq 25n^3 + 10$

The next step logical step for me is to prove that $25n^3 + 10 \geq 5(k+1)^3 + 2$ but I have no idea how.

$\endgroup$
  • $\begingroup$ Suggest to use \geq ($\geq$) instead of >= (check MathJax basic tutorial and quick reference if you are interested) $\endgroup$ – Sil Oct 13 '19 at 21:15
  • $\begingroup$ Thank you for the advice. $\endgroup$ – heky__ Oct 13 '19 at 21:24
4
$\begingroup$

You have $5^{n+1}=5\cdot 5^n\geq 5(5n^3+2)=25n^3+10$, we need to show that

$5^{n+1}\geq 5(n+1)^3+2=5(n^3+3n^2+3n+1)+2=(5n^3+15n^2+15n+5)+2$

We know that $n\geq 4$, so if we write:

$25n^3=5n^3+20n^3\geq 5n^3+80n^2\geq 5n^3+15n^2+65n^2\geq 5n^3+15n^2+260n$

$\geq 5n^3+15n^2+15n+5=5(n+1)^3$

Where we substitute one $n$ by $4$ in every step and derive the result like that.

So: $25n^3+2\geq 5(n+1)^3+2$, which ends the inductive proof.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks, what a beautiful solution. In the first line, where you distribute 5 into $(5n^3 + 2)$ is a small mistake, it should yield $25n^3 + 10$ not $25n^3 +2$. However, it doesn't affect the overall principle on how to approach those kind of problems. $\endgroup$ – heky__ Oct 13 '19 at 21:40
  • $\begingroup$ @heky__ Thanks for pointing that out. I will edit that. $\endgroup$ – Cornman Oct 13 '19 at 21:47
2
$\begingroup$

Since you have gotten answers with induction, I am providing a different approach---a combinatorial proof. Here, $\mathbb{Z}/5\mathbb{Z}$ is the set of integers modulo $5$.

Let $[n]:=\{1,2,\ldots,n\}$. For $n\geq 4$, consider the set $$S:=\big\{(a,b,c,k)\,\big|\,a,b,c\in[n]\text{ and }k\in\mathbb{Z}/5\mathbb{Z}\big\}$$ and $$T:=(\mathbb{Z}/5\mathbb{Z})^n=\big\{(t_1,t_2,\ldots,t_n)\,\big|\,t_i\in(\mathbb{Z}/5\mathbb{Z})\text{ for }i=1,2,\ldots,n\big\}\,.$$ Define $f:S\to T$ as follows.

  1. If $a$, $b$, and $c$ are pairwise distinct, we set $f(a,b,c,k):=(x_1,x_2,\ldots,x_n)$ with $x_i:=k+1$ for all $i\in[n]\setminus\{a,b,c\}$, $x_a:=k+2$, $x_b:=k+3$, and $x_c:=k+4$.
  2. If $\big|\{a,b,c\}\big|=2$, then there are three subcases: $(a,b,c)=(a,a,c)$, $(a,b,c)=(a,b,a)$, and $(a,b,c)=(a,b,b)$. We set $f(a,b,c,k):=(x_1,x_2,\ldots,x_n)$ with $x_i:=k+1$ for all $i\in[n]\setminus\{a,b,c\}$. For $i\in\{a,b,c\}$, we define $x_i$ differently in each case.
    • If $(a,b,c)=(a,a,c)$, then $x_a:=k+2$ and $x_c:=k+3$.
    • If $(a,b,c)=(a,b,a)$, then $x_a:=k+4$ and $x_b:=k+2$.
    • If $(a,b,c)=(a,b,b)$, then $x_a:=k+3$ and $x_b:=k+4$.
  3. If $a=b=c$, then we set $f(a,b,c,k):=(x_1,x_2,\ldots,x_n)$ with $x_i:=k+1$ for all $i\in[n]\setminus\{a,b,c\}$, and $x_a:=k+2$.

Note that $f$ is an injective function (why?). Furthermore, $T\setminus f(S)$ contains at least five elements of the form $(t,t,t,\ldots,t)$ where $t\in(\mathbb{Z}/5\mathbb{Z})$. Therefore, $$5^n=|T|=\big|f(S)\big|+\big|T\setminus f(S)\big|=|S|+\big|T\setminus f(S)\big|\geq|S|+5\,.$$ Since $|S|=5n^3$, we conclude that $$5^n\geq 5n^3+5>5n^3+2\,.$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You can make life easier by dividing by $5$. I'll then substitute $m = n-1$ so that we are considering $m \geq 3$:

$$5^{m} \geq (m+1)^3+\frac{2}{5}$$ Since $5^m$ and $m+1$ are both integers, this is equivalent to $$5^m > (m+1)^3$$

That's much easier by induction; it's trivially true when $m = 3$, and then the inductive step just involves taking cube roots.


Your way will work. I think the easiest way to do that is to find the roots of $25n^3+10-5(n+1)^3-2$ (or rather, don't find them, but use the intermediate value theorem to bound them), and then use the fact that this cubic function is increasing for inputs greater than the last root.

| cite | improve this answer | |
$\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.