Is there any way to simplify my proof by induction?

  • #1
murshid_islam
442
17
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

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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:
  • #3
mathman
Science Advisor
8,087
550
Your presentation has arithmetic errors.
 
  • #4
LuisP
8
0
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
 
  • #5
murshid_islam
442
17
Your presentation has arithmetic errors.
Can you point out at which line? I can't find them.
 
  • #6
36,708
8,707
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)! ##
 
  • #7
mathman
Science Advisor
8,087
550
Can you point out at which line? I can't find them.
##(k+1)^2=k^2+2k+1## (secod line)
 
  • #8
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,697
1,274
##(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
  • #9
murshid_islam
442
17
##(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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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
murshid_islam
442
17
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
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
murshid_islam
442
17
I divided through by ##n##. I didn't realise that might seem so obscure!
I had a brain fart.
 
  • #14
murshid_islam
442
17
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)!##
 

Suggested for: Is there any way to simplify my proof by induction?

Replies
76
Views
2K
Replies
11
Views
666
  • Last Post
Replies
2
Views
278
Replies
8
Views
750
  • Last Post
Replies
1
Views
136
Replies
29
Views
590
  • Last Post
Replies
2
Views
724
Replies
10
Views
618
Top