Prove using finite induction that $4^n > n^4$ for all $n > 4$?

4.7k Views Asked by At

Well, $4^5 = 1024$ and $5^4 = 625$, so the statement certainly holds when n = 5. Suppose that for some integer k ≥ 5, the conclusion holds. That is 

$4^k > k^4$. 

Consider the case $n = k + 1$. Note that $4^{k+1} = 4 \cdot 4^k$. Also 

$(k+1)^4 = k^4 + 4k^3 + 6k^2 + 4k + 1$. 

Now $k ≥ 5$, so $4k^3 < k^4$, $6k^2 < k^4$, and $4k + 1 < k^4$. So 

$$(k+1)^4 < 4\cdot k^4.$$ 

Can't go ahead of this.

1

There are 1 best solutions below

3
On BEST ANSWER

You have just shown that $(k+1)^4 <4\cdot k^4$ and we know that, by the inductive hypothesis, $k^4 <4^k $ so we have $(k+1)^4 <4\cdot 4^k=4^{k+1} $ and we have completed the inductive step.