0

This is a practice problem, and but I am having trouble what I should do. I am new to proof writing, so I am a little bit uncomfortable with induction.

Question: Prove by induction that for any integer $n \geq 7, 3^n \leq n!$, where $n! = n(n-1)(n-2)...$.

My Attempt:

Suppose $P(n)$ is the assertion: $n \geq 7, 3^n \leq n!$. First we need to prove that the assertion for the base case is true. That means showing that when $n = 7, 3^n \leq 7!$, so

\begin{align*} 3^7 &\leq 7! \\ 2187 &\leq (7)(6)(5)(4)(3)(2)(1) \\ 2187 &\leq 5040 \end{align*}

This confirms that the inequality holds for $n = 7$

Assume that the assertion $P(n)$ is true for $n = k$, such that $P(k)$ is true. That means to assume that $3^k \leq k!$ (Inductive Hypothesis) is true

Then by making the inductive step, by using the inductive hypothesis, it follows that $P(k + 1)$ is true. $$3^{k+1} \leq (k + 1)!$$

We want to show that if $P(k + 1)$ follows $P(k)$, and the conclusion is true along with the base case, then this will prove that $P(n)$ is true

\begin{align*} 3^{k+1} &\leq (k + 1)! \\ (3)^k (3)^1 &\leq (k + 1)k! \\ \end{align*}

This is where I am lost, and do not know how to proceed.

Any help is appreciated.

maraik2002
  • 303
  • Going from case $n=k$, you multiple left side by three and the right side by something greater than three, correct? – Vasili Dec 03 '20 at 18:34
  • Obviously for $k\ge 7, k \ge 3$. However do not start the proof from the conclusion. – player3236 Dec 03 '20 at 18:35
  • Two things: (1) you wrote $P(n)$ incorrectly. $P(n)$ is the statement $3^n \leq n!$. Note that $P(n)$ is false for e.g. $n=1$ but true for e.g. $n=10$. You want to prove that $P(n)$ is true for $n \geq 7$. (2) you've almost got it - just remember that if $a, b, c, d > 0$ and $a < b$ and $c < d$ then $ac < bd$. – roundsquare Dec 03 '20 at 19:05

1 Answers1

1

Consider the following for any $k\geq 7$:

$$3^{k+1} = 3\times 3^k \leq 3 (k!)\leq k(k!) = (k+1)!.$$ Here, the first inequality holds from $P(k)$ and the second inequality is because $k\geq7>3$.

Hence, we showed that when $P(k)$ holds, $P(k+1)$ also holds.

Explorer
  • 3,147