1

Say I have $2^n +1 < n! -n$ for all $n \ge 4$, and $n$ is an integer.

My inductive steps says, consider a $k$ that is a arbitrary integer, assuming $P(k)$.

Thus, $$\begin{align} 2^{k+1} +1 = 2^k \cdot 2 +1 \\ 2^k\cdot 2+1\overset{\mathrm{IH}}{<} 2(k!-k) < ((k+1)!-k) \\\text{Therefore, we have proven this my mathematical induction.} \end{align}$$

I am not too sure on how to use < in mathematical induction. I based this off an example I saw, and wondering it is valid, and maybe some calcification on what this works (if it does)...

DippyDog
  • 313

2 Answers2

1

Assuming $P(k)$ you have to show $P(k+1)$. In other words, assuming that $$2^k + 1 < k! - k,\tag{$P(k)$}$$ you have to show that $$2^{k+1} + 1 < (k+1)! - (k+1). \tag{$P(k+1)$}$$ Your inductive hypothesis $P(k)$ can be rewritten as $$2^k < k! - k - 1\tag{*}\label{*}.$$ Thus \begin{align} 2^{k+1}+1 &= 2\cdot 2^k + 1\\ &\stackrel{\eqref{*}}{<}2(k!-k-1)+1\\ &=2k! - 2k -1\\ &<2k!-(k+1)\\ &<(k+1)!-(k+1). \end{align}

posilon
  • 2,253
1

In general, mathematical induction on the statement $P(k)$ provides a proof strategy requiring the following steps:

  1. Prove the base case: $P(k=0)$ is true

  2. Assume the inductive hypothesis: $P(k)$ is true for some $k \in \mathbb{N}.$

  3. Show that as a result of the above: $P(k+1)$ is true.

  4. The proof is complete for all $k$.

In this case, your $P(k)$ is the statement $2^k + 1 < k! - k \ \forall k \geq 4 $. Let us show $P(k=4)$ holds (the smallest value for the inequality): $2^4 + 1 = 17 < 4! - 4 = 24-4=20$ is clearly satisfied.

Now let us assume $2^k + 1 < k! - k$ for some $k \geq 4$ (since we've already proven the case $k=4$). We want to use this to prove $2^{k+1}+ 1 < (k+1)! - (k+1)$

As you've mentioned, $2^{k+1}=2*2^{k}$. Recalling the inductive step above, $2*2^{k} < 2*(k!-k - 1).$ Certainly $2k! - 2k - 2 = 2k! - 2*(k+1) < (k+1)! - (k+1)$.

This is because $2k! < (k+1)! = (k+1)k!\ \forall k > 1$.

Now, chaining together the last few inequalities, we arrive at $2*2^k=2^{k+1} < (k+1)! - (k+1)$

Jacob A
  • 579
  • The implication $P(k) \Rightarrow P(k+1)$ must be proven for every $k \geq 4$. If you prove it just for $k \geq 5$ then you haven't proven that $P(5)$ is true. – posilon Feb 25 '21 at 00:56
  • @posilon by "for some" I mean an arbitrary integer. And I've taken $P(5)$ as the inductive step (i.e. the next in the chain). – Jacob A Feb 25 '21 at 01:04
  • You have proven $P(4)$ and that $P(k)$ implies $P(k+1)$ for every $k \geq 5$. But nothing to guarantee that $P(5)$ is true. – posilon Feb 25 '21 at 01:49
  • In order to prove $P(5)$ as the next in the chain, you should prove that $P(4) \Rightarrow P(5)$, i.e. you should prove the inductive step for $k=4$ as well. – posilon Feb 25 '21 at 01:53