Is there any way to simplify my proof by induction?

[murshid_islam]

TL;DR

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! < –k² from the induction hypothesis for n = k]
$< (k+1)! + 0$ ; [2k – k² = 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.

 

[PeroK]

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.

 

[mathman]

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.

 

[Mark44]

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.

$< 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! < –k² from the induction hypothesis for n = k]
$< (k+1)! + 0$ ; [2k – k² = k(2 – k) < 0 for k > 2]

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

 

[mathman]

Can you point out at which line? I can't find them.

$(k+1)^2=k^2+2k+1$ (secod line)

 

[SammyS]

$(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]

$(k+1)^2=k^2+2k+1$ (secod line)

That line (k + 1)² + 1 was expanded and rearranged as k² + 1 + 2k + 1.

 

[PeroK]

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?

 

[PeroK]

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)!$