# Is there any way to simplify my proof by induction?

murshid_islam
TL;DR Summary
My proof by induction looks way too contrived. Is there a way to simplify it?
I'm trying to prove the statement ##n^2 + 1 < n!## for ##n \geq 4##. My proof by induction looks way too contrived. Is there a way to simplify it? Here's what I got.

For n = 4, ##n^2 + 1 = 17 < 4!##. So, the statement is true for n = 4. Now let's assume it's true for n = k, that is, ##k^2 + 1 < k!##

Now, for n = k+1,
##(k+1)^2 + 1 ##
##= (k^2 + 1) + 2k + 1##
##< k! + 2k + 1## ; [from the induction hypothesis for n = k]
##< k\cdot k! + 2k + 1##
##= (k+1-1)k! + 2k + 1##
##= (k+1)k! - k! + 2k + 1##
##= (k+1)! + 2k + (1 - k!)##
##< (k+1)! + 2k - k^2## ; [because 1 – k! < –k2 from the induction hypothesis for n = k]
##< (k+1)! + 0## ; [2k – k2 = k(2 – k) < 0 for k > 2]

Therefore, we have ##(k+1)^2 + 1 < (k+1)! ##

I was wondering if there's an easier way to do the n = k + 1 part.

Last edited:

## Answers and Replies

Science Advisor
Homework Helper
Gold Member
2022 Award
It doesn't seem like a good example of induction, as you don't really need the inductive hypothesis. If we look for the cases where ##n^2 + 1 \ge n!##, then we have ##n + 1 \ge n + \frac 1 n \ge (n-1)!##.

Now, if ##n \ge 4##, then ##(n-1) \ge 3## and ##(n-1)! \ge 2(n-1)##. So we can look for ##n## such that: ##n +1 \ge 2n - 2## and so ##n \le 3##, which contradicts ##n \ge 4##.

You could, of course, logically use this in the inductive step. But, it shows that induction itself is not very helpful in this case.

Last edited:
Science Advisor
Your presentation has arithmetic errors.

LuisP
Another way is to go continuous, using the gamma function.

$$n!= Γ(n+1)$$

the gamma function is known to grow very fast. So we can assume that at some value of x the factorial will be above any polynomial.

You can try to solve the equation numerically,
$$Γ(x+1) = x^2+1$$

Using python scipy root_scalar, I get the result 3.6467225149185953

murshid_islam
Your presentation has arithmetic errors.
Can you point out at which line? I can't find them.

Mentor
For n = 4, ##n^2 + 1 = 17 < 4!##. So, the statement is true for n = 4. Now let's assume it's true for n = k, that is, ##k^2 + 1 < k!##

Now, for n = k+1,
##(k+1)^2 + 1 ##
##= (k^2 + 1) + 2k + 1##
##< k! + 2k + 1## ; [from the induction hypothesis for n = k]
You want the next inequality to be ##< (k + 1)!##
If you can show that ##(k + 1)! - k! - 2k - 1 > 0## that's equivalent to saying that ##k! + 2k + 1 < (k + 1)!##.
The first inequality above is equivalent to ##k!(k + 1 - 1) - 2k - 1 > 0##, or ##k! \cdot k - 2k - 1 > 0##. That should be fairly easy to do.
murshid_islam said:
##< k\cdot k! + 2k + 1##
##= (k+1-1)k! + 2k + 1##
##= (k+1)k! - k! + 2k + 1##
##= (k+1)! + 2k + (1 - k!)##
##< (k+1)! + 2k - k^2## ; [because 1 – k! < –k2 from the induction hypothesis for n = k]
##< (k+1)! + 0## ; [2k – k2 = k(2 – k) < 0 for k > 2]

Therefore, we have ##(k+1)^2 + 1 < (k+1)! ##

Science Advisor
Can you point out at which line? I can't find them.
##(k+1)^2=k^2+2k+1## (secod line)

Staff Emeritus
Science Advisor
Homework Helper
Gold Member
##(k+1)^2=k^2+2k+1## (secod line)
This can be written as ##(k^2+1)+2k## .

Therefore, no error at that point.

murshid_islam
murshid_islam
##(k+1)^2=k^2+2k+1## (secod line)
That line (k + 1)2 + 1 was expanded and rearranged as k2 + 1 + 2k + 1.

SammyS
Science Advisor
Homework Helper
Gold Member
2022 Award
TL;DR Summary: My proof by induction looks way too contrived.
It may be worth re-emphasising that using induction itself is contrived in this case and that's partly why the inductive step gets messy. It looks more natural to prove directly that$$n^2 + 1 < n!$$rather then$$k! + 2k + 1 \le (k+1)!$$In other words, using the inductive hypothesis makes things harder.

murshid_islam
If we look for the cases where ##n^2 + 1 \ge n!##, then we have ##n + 1 \ge n + \frac 1 n \ge (n-1)!##.
I did not get this part: ##n + \frac 1 n \ge (n-1)!## Can you elaborate?

Science Advisor
Homework Helper
Gold Member
2022 Award
I did not get this part: ##n + \frac 1 n \ge (n-1)!## Can you elaborate?
I divided through by ##n##. I didn't realise that might seem so obscure!

murshid_islam
I divided through by ##n##. I didn't realise that might seem so obscure!
I had a brain fart.

murshid_islam
By the way, here's a simpler version of my original proof:

For ##n = k+1##,
##(k+1)^2 + 1 ##
##= (k^2 + 1) + 2k + 1##
##< k! + 2k + 1## ; [from the induction hypothesis for n = k]
##< k \cdot k! + k^2 + 1##
##< k \cdot k! + k!## ;[from the induction hypothesis for n = k]
##= (k+1)!##