Proof by induction: $5^n \geq 5n^3 + 2$ for $n \geq 4$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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