Question

Show by maths induction that for integers greater than 5, `4^n>n^4`?

Answer 1

Induction Proof - Hypothesis

We seek to prove that the expression:

`4^n gt n^4 \ \ \ AA n gt 5` ..... [A]

Induction Proof - Base case:

When `n=6`, the first integer greater than `5`, we have:

`LHS = 4^6 = 4096`
`RHS = 6^4 = 1296`

And `LHS > RHS`, So the given result is true when `n=6`. (Note We can also readily verify that the expression also holds for `n=0,1,5` but fails for `n=4,5`, so we can readily extend the proof to include the case `n=5`

Induction Proof - General Case

Now, Let us assume that the given result [A] is true when `n=m`, for some `m in NN, m ge 6`, in which case for this particular value of `m` we have:

`4^m gt m^4 iff m^4 lt 4^m` ..... [B]

Now, consider the RHS expression of [A] when we have `n=m+1`:

`RHS = (m+1)^4`

We can expand this using the Binomial Expansion:

`RHS = m^4 + 4m^3 + 6m^2 +4m + 1`

Now, `m ge 6` and so:

`4m^3 < m^4`
`6m^2 lt m^4`
`4m+1 lt m^4`

And so:

`RHS < m^4 + m^4 + m^4 +m^4`
`\ \ \ \ \ \ \ \ < 4 xx m^4`
`\ \ \ \ \ \ \ \ < 4 xx 4^m \ \ \` (using [B])
`\ \ \ \ \ \ \ \ < 4^(m+1)`

Equivalently:

`4^(m+1) > (m+1)^4`

Which is the given expression [A], with `n=m+1`

Induction Proof - Summary

So, we have shown that if the given result [A] is true for `n=m`, then it is also true for `n=m+1` where `m ge 6`. But we initially showed that the given result was true for `n=6` so it must also be true for `n=7, n=8, n=9, ...` and so on.

Induction Proof - Conclusion

Then, by the process of mathematical induction the given result [A] is true for `n in NN`

Hence we have:

`4^n gt n^4 \ \ \ AA n gt 5 \ \ \ \` QED