Mathematical-Reasoning · Unit 13 · Video 1 · Interactive Practice

When Ordinary Induction Falls Short: n! vs 2ⁿ and Primes

IKey Formulas

Statement	In symbols	How to use it
$n$ factorial	$n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n$ , and $0! = 1$	The product of the first $n$ natural numbers
Each factorial from the previous one	$n! = n \cdot (n-1)!$	Multiplying $k!$ by $k + 1$ gives $(k+1)!$
Scratch inductive step for $n! > 2^n$	$(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k > 2^{k+1}$	The middle link uses $P(k)$ ; the last uses $k + 1 > 2$
$n$ is composite	$n = a \cdot b$ with $1 < a < n$ and $1 < b < n$	Each factor is at most $\frac{n}{2}$ , which is less than $n - 1$ when $n > 2$

Key Insight: Ordinary induction has basis step $P(1)$ and an inductive step from $P(k)$ to $P(k+1)$ . The claim $n! > 2^n$ is false for $n = 1, 2, 3$ , so it needs a later starting point; a composite number splits into factors that are never $n - 1$ , so its inductive step needs the statement for smaller numbers than $k$ .

IIThe Race Between $n!$ and $2^n$

Going from $n$ to $n + 1$ multiplies $n!$ by $n + 1$ but multiplies $2^n$ only by $2$ .

n 4

IIIWhat the Inductive Step Uses

The chain $(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k > 2^{k+1}$ needs $P(k)$ and $k + 1 > 2$ .

k 4

IVSplitting a Composite Number

Every split $n = a \cdot b$ of a composite number produces factors at most $\frac{n}{2}$ , never $n - 1$ .

💡 The next video moves the basis step to $P(4)$ and proves $n! > 2^n$ for every $n \geq 4$ ; the one after it lets the inductive step assume $P(2), P(3), \ldots, P(k)$ all at once.

VQuiz Questions

Problem 1 · The Next Factorials

Given: $5! = 120$ — find $7!$ using $n! = n \cdot (n-1)!$ .

✅ Correct!

6! = 6 \cdot 120 = 720

, then

7! = 7 \cdot 720 = 5040

❌ Not quite.

720

6! = 6 \cdot 5!

; one more step, multiplying by

7

, is still needed.

❌ Not quite.

840 = 7 \cdot 5!

skips the factor

6

: the identity gives

7! = 7 \cdot 6!

, not

7 \cdot 5!

❌ Not quite.

727 = 7 + 6!

adds the next number; a factorial multiplies by it:

7! = 7 \cdot 6!

Show solution

Apply $n! = n \cdot (n-1)!$ twice, starting from $5! = 120$ :

6! = 6 \cdot 5! = 6 \cdot 120 = 720

7! = 7 \cdot 6! = 7 \cdot 720 = 5040

Check against the definition: $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 = 5040$ . So $7! = 5040$ .

Problem 2 · Justifying the Last Link

Given: $k \in \mathbb{N}$ with $k \geq 4$ and the chain $(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k > 2^{k+1}$ — which fact justifies the last inequality $(k+1) \cdot 2^k > 2^{k+1}$ ?

✅ Correct! Multiplying

k + 1 > 2

by the positive number

2^k

keeps the direction, and

2 \cdot 2^k = 2^{k+1}

❌ Not quite.

P(k)

justifies the middle link,

(k+1) \cdot k! > (k+1) \cdot 2^k

; the last link contains no factorial at all.

❌ Not quite. That identity is the first link, the equality

(k+1)! = (k+1) \cdot k!

; it says nothing about powers of

2

❌ Not quite. That inequality is true but compares with

k \cdot 2^k

, not with

2^{k+1} = 2 \cdot 2^k

; the factor to beat is

2

, not

k

Show solution

Since $k \geq 4$ , $k + 1 \geq 5 > 2$ . Because $2^k > 0$ , multiplying both sides of $k + 1 > 2$ by $2^k$ keeps the direction:

(k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}.

The three links use three different facts: the identity $n! = n \cdot (n-1)!$ with $n = k + 1$ for the equality, the hypothesis $P(k)$ (multiplied by $k + 1 > 0$ ) for the middle inequality, and $k + 1 > 2$ for the last one.

Problem 3 · Where the Last Link Holds

Given: the inequality $(k+1) \cdot 2^k > 2^{k+1}$ — find exactly which natural numbers $k$ make it true.

✅ Correct! Dividing by

2^k > 0

turns it into

k + 1 > 2

, which holds exactly when

k \geq 2

. The proof needs

k \geq 4

only for the hypothesis

P(k)

❌ Not quite.

k \geq 4

is where

P(k)

becomes true. This link is weaker: at

k = 2

3 \cdot 2^2 = 12 > 8 = 2^3

already.

❌ Not quite. At

k = 1

both sides equal

4

2 \cdot 2^1 = 4 = 2^2

, and

4 > 4

is false.

❌ Not quite.

k = 2

works as well:

3 \cdot 2^2 = 12 > 8 = 2^3

Show solution

Since $2^{k+1} = 2 \cdot 2^k$ and $2^k > 0$ , dividing both sides by $2^k$ gives an equivalent inequality:

(k+1) \cdot 2^k > 2 \cdot 2^k \iff k + 1 > 2 \iff k > 1.

So the link holds exactly for $k \geq 2$ . At $k = 1$ : $2 \cdot 2 = 4 = 2^2$ , equal rather than greater. At $k = 2$ : $3 \cdot 4 = 12 > 8$ . At $k = 3$ : $4 \cdot 8 = 32 > 16$ . For $k = 2$ and $k = 3$ the chain still breaks, but at the middle link, because $P(2)$ and $P(3)$ are false.

Problem 4 · Which Cases Does $91$ Need?

Given: $91 = 7 \cdot 13$ , and $P(m)$ : " $m$ is prime or a product of primes" — which statements does this split use to show that $91$ is a product of primes?

✅ Correct! Each factor is prime, so

91 = 7 \cdot 13

is a product of primes; both factors are far below

90

❌ Not quite.

P(90)

is what ordinary induction assumes at

k + 1 = 91

, but

90

is not a factor of

91

, so it does not help.

❌ Not quite.

45 + 46 = 91

is a sum, not a product; a split into factors is what the definition of composite provides.

❌ Not quite.

91 = 1 \cdot 91

does not satisfy

1 < a < 91

, and

P(91)

is the statement being proved.

Show solution

$91$ is composite: $91 = 7 \cdot 13$ with $1 < 7 < 91$ and $1 < 13 < 91$ . To write $91$ as a product of primes it is enough to know that $7$ and $13$ are each prime or a product of primes, that is, $P(7)$ and $P(13)$ . Both are prime, so $91 = 7 \cdot 13$ is the factorisation.

Neither factor is $90$ : each is at most $\frac{91}{2}$ , which is less than $90$ . Ordinary induction, which assumes only $P(90)$ , gives no help here; the inductive step needs statements for numbers well below $k = 90$ .

Solved: 0 / 4

When Ordinary Induction Falls Short: n! vs 2ⁿ and Primes

IKey Formulas

IIThe Race Between n!n!n! and 2n2^n2n

IIIWhat the Inductive Step Uses

IVSplitting a Composite Number

VQuiz Questions

IIThe Race Between $n!$ and $2^n$