# Mathematical induction proof for integers

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

• 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) Commented Feb 20, 2023 at 20:11
• 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. Commented Feb 20, 2023 at 20:16
• 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$ Commented Feb 21, 2023 at 8:44

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}$$

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}.$$