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

AI Thread Summary
The discussion centers on simplifying a proof by induction for the statement n^2 + 1 < n! for n ≥ 4. The original proof appears overly complex, and participants suggest that induction may not be the best approach, recommending a direct proof instead. They highlight that the inductive step can become messy and that proving the inequality directly may be more straightforward. Additionally, there are mentions of arithmetic errors in the proof, with suggestions to clarify certain inequalities. Ultimately, a simpler version of the proof is proposed, demonstrating that the inductive hypothesis can be streamlined.
murshid_islam
Messages
468
Reaction score
21
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:
Mathematics news on Phys.org
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:
Your presentation has arithmetic errors.
 
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
 
mathman said:
Your presentation has arithmetic errors.
Can you point out at which line? I can't find them.
 
murshid_islam said:
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)! ##
 
murshid_islam said:
Can you point out at which line? I can't find them.
##(k+1)^2=k^2+2k+1## (secod line)
 
mathman said:
##(k+1)^2=k^2+2k+1## (secod line)
This can be written as ##(k^2+1)+2k## .

Therefore, no error at that point.
 
  • Like
Likes murshid_islam
mathman said:
##(k+1)^2=k^2+2k+1## (secod line)
That line (k + 1)2 + 1 was expanded and rearranged as k2 + 1 + 2k + 1.
 
  • #10
murshid_islam said:
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.
 
  • #11
PeroK said:
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?
 
  • #12
murshid_islam said:
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!
 
  • #13
PeroK said:
I divided through by ##n##. I didn't realise that might seem so obscure!
I had a brain fart.
 
  • #14
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)!##
 
Back
Top