3
$\begingroup$

Use mathematical induction to prove that $n! > 4^n$ for $n \geq 9$.

My attempt:

  1. Base case: For $n=9$, we have $9! = 362880$ and $4^9 = 262144$

  2. Since $9! > 4^9$, the statement is true for $n=9$

  3. Inductive hypothesis: Assume that $k! > 4^k$ for some positive integer $k \geq 9$

  4. Inductive step: We want to show that $(k+1)! > 4^{k+1}$

  5. We start with $(k+1)!$, which can be written as $(k+1) \cdot k!$

  6. Using the inductive hypothesis, we know that $k! > 4^k$

  7. Substituting this into the expression for $(k+1)!$, we get $(k+1)! > (k+1) \cdot 4^k$

  8. To complete the proof, we need to show that $(k+1) \cdot 4^k > 4^{k+1}$

  9. Dividing both sides by $4^k$, we get $k+1 > \frac{4^{k+1}}{4^k}$

  10. Since $k \geq 9$, we can plug in $k=9$ , through calculating $9+1 > \frac{4^{9+1}}{4^9}$ , and we get $10 > 4$

  11. Since $(k+1)$ is greater than this value, we have $(k+1) \cdot 4^k > 4^{k+1}$

  12. Therefore, we have shown that $(k+1)! > 4^{k+1}$, which completes the inductive step

  13. By the principle of mathematical induction, we have proven that $n! > 4^n$ for all $n \geq 9$

$\endgroup$
3
  • 1
    $\begingroup$ FWIW, fixing the proof here after being pointed out the flaw invalidates the answers themselves, which is generally frowned upon. Also, if you're dividing 4^(k+1) by 4^k, you get just 4, not that 4^(k+1)/4^k you wrote - I mean, they are numerically equal, but the whole point of this division is to simplify the expression before numerical substitutions, not make it more complicated later on (similarly, 2x divided by 2 is just x, not 2x/2, although both are in fact equal) $\endgroup$
    – user213769
    Commented Feb 20, 2023 at 20:11
  • $\begingroup$ also, strictly speaking, your new step 10 can/should be just laid out as "since we assumed k >= 9, k > 3 is always true, which concludes the proof" - your step 9 is just "k+1 > 4" which gives trivial "k > 3" as a result here. I'd also argue with the phrasings you use - "using the inductive hypothesis, we know that"... actually, we don't know that, we assume that. Instead of "Substituting this into the expression for (k+1)!", I'd say "Substituting (k+1) into the expression for k" or something similar etc. English is not my first language, but still something feels off about your wordings. $\endgroup$
    – user213769
    Commented Feb 20, 2023 at 20:16
  • $\begingroup$ Note that you may not use a calculator for the initialization : $9!=2.4.6.8.3.5.7.9=2^7.3^4.5.7>2^7.8^2.35>2^7.2^6.32=2^{18} = 4^9$ $\endgroup$ Commented Feb 21, 2023 at 8:44

2 Answers 2

7
$\begingroup$

No, your proof is not correct. You are correct up to this point:

$$(k+1)\cdot 4^k > 4^{k+1}$$

However, you then claim that by dividing both sides by $4^k$, you get

$$k+1>\frac{4}{4^k}$$ which is not true. In fact, dividing both sides by $4^k$, you get

$$k+1 > \frac{4^{k+1}}{4^k}\neq \frac{4}{4^k}$$

$\endgroup$
3
$\begingroup$

It is easy to see that when you increment $n$, the factorial is multiplied by $n+1$ and the power by $4$, so the LHS will quickly exceed the RHS.

Formally, for all $n\ge9$ (of course implying $n+1>4$), $$(n+1)!=(n+1)n!>(n+1)4^n>4^{n+1}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .