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

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.

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

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.

• 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. – heky__ Oct 13 '19 at 21:40
• @heky__ Thanks for pointing that out. I will edit that. – Cornman Oct 13 '19 at 21:47

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

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.