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

Extended Induction: Start the Basis Step at Any Integer M

IKey Formulas

Formula	Name	Role
$M \in T$ and, for every $k \in \mathbb{Z}$ with $k \ge M$ , $k \in T \to (k + 1) \in T$	Hypotheses of the Extended Principle ( $M \in \mathbb{Z}$ , $T \subseteq \mathbb{Z}$ )	The two conditions to verify
$\{n \in \mathbb{Z} \mid n \ge M\} \subseteq T$	Conclusion of the Extended Principle	Every integer from $M$ on is in $T$
Basis $P(M)$ ; for $k \ge M$ : $P(k) \to P(k + 1)$	Proof by induction starting at $M$	Proves $P(n)$ for every $n \in \mathbb{Z}$ with $n \ge M$
$(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^k > 2 \cdot 2^k = 2^{k + 1}$	Inductive step for $n! > 2^n$	Uses $P(k)$ , then $k + 1 > 2$ (true since $k \ge 4$ )

Key Insight: The basis step decides where the guarantee starts: induction from $M$ covers every integer $n \ge M$ and says nothing about the integers below $M$ .

IIVisualization 1 — Knock Over Domino $M$

A true basis $P(M)$ plus a step from $M$ on proves $P(n)$ for every $n \ge M$ , and nothing below $M$ .

Open sentence Basis M 4 Falls 0

IIIVisualization 2 — Where $k \ge 4$ Enters the Step

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

k 4

IVVisualization 3 — Find the Starting Value $M$

Where does the run of true cases begin? That first case is the basis $M$ a proof would use.

Question

💡 Ten checked cases only support a conjecture "for each $n \in \mathbb{N}$ , if $n \ge M$ , then $P(n)$ "; a proof still needs the basis $P(M)$ and the inductive step for every $k \ge M$ .

VQuiz Questions

Problem 1 · The Basis Step

Given: a proof by induction of "for each $n \in \mathbb{N}$ with $n \ge 6$ , $2^n > (n + 1)^2$ ." Which statement must the basis step verify?

✅ Correct! The starting integer is

M = 6

, and

2^6 = 64 > 49 = 7^2

, so

P(6)

is true.

❌ Not quite. The statement starts at

n = 6

, so the basis is

P(6)

, not

P(1)

. Here

P(1)

is even false:

2 > 4

fails.

❌ Not quite.

P(5)

is not part of the claim, and it is false:

2^5 = 32 < 36 = 6^2

. The basis is the first integer the claim covers,

M = 6

❌ Not quite. A basis at

7

would prove

P(n)

only for

n \ge 7

and leave

n = 6

unproved. The basis must be

P(6)

Show solution

The claim has the form "for each $n \in \mathbb{N}$ , if $n \ge M$ , then $P(n)$ " with $M = 6$ and $P(n)$ : $2^n > (n + 1)^2$ . The basis step of the Extended Principle proves $P(M) = P(6)$ :

2^6 = 64 > 49 = (6 + 1)^2.

The inductive step then proves $P(k) \to P(k + 1)$ for every $k \ge 6$ .

Problem 2 · Where the Start at 4 Is Used

Given: the inductive step for $n! > 2^n$ : let $k \in \mathbb{N}$ with $k \ge 4$ and assume $k! > 2^k$ ; then $(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^k > 2 \cdot 2^k = 2^{k + 1}$ . Where does the step use $k \ge 4$ ?

✅ Correct!

k \ge 4

gives

k + 1 \ge 5 > 2

; multiplying

k + 1 > 2

2^k > 0

gives the second link of the chain.

❌ Not quite.

k! > 2^k

is the inductive hypothesis

P(k)

: it is assumed, not derived from

k \ge 4

❌ Not quite.

k + 1 > 0

holds for every natural number

k

; it needs no lower bound like

4

❌ Not quite. The link

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

is false when

k = 1

(

4 > 4

fails), so it needs a lower bound on

k

; the proof gets it from

k \ge 4

Show solution

The chain has two links.

Link (2): multiply the hypothesis $k! > 2^k$ by $k + 1 > 0$ (true for every $k \in \mathbb{N}$ ): $(k + 1)! > (k + 1) \cdot 2^k$ .

Link (3): since $k \ge 4$ , $k + 1 > 2$ ; multiplying by $2^k > 0$ gives $(k + 1) \cdot 2^k > 2 \cdot 2^k = 2^{k + 1}$ .

So $k \ge 4$ is used exactly once, to get $k + 1 > 2$ . (Any $k \ge 2$ would do there; the basis is $P(4)$ because $P(3)$ is false: $3! = 6 < 8 = 2^3$ .)

Problem 3 · Build the Inductive Step

Given: the conjecture "for each $n \in \mathbb{N}$ , if $n \ge 2$ , then $3^n > 1 + 2^n$ ." Let $k \ge 2$ and assume $3^k > 1 + 2^k$ . Which chain correctly proves $3^{k + 1} > 1 + 2^{k + 1}$ ?

✅ Correct! Each step is justified: multiply the hypothesis by

3

, then use

3 > 1

and

3 \cdot 2^k > 2 \cdot 2^k

❌ Not quite.

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

, not

3^k + 3

(for

k = 2

27 \ne 12

❌ Not quite.

3 \cdot 2^k \ne 2^{k + 1}

;

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

. The chain needs

3 \cdot 2^k > 2 \cdot 2^k

as its own step.

❌ Not quite.

3^{k + 1} > 2^{k + 1}

does not give

3^{k + 1} > 1 + 2^{k + 1}

(compare

3 > 2

with

3 > 3

), and this argument never uses the hypothesis

P(k)

Show solution

Assume $3^k > 1 + 2^k$ (inequality (1)). Multiply (1) by $3 > 0$ :

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

Since $3 > 1$ and $3 \cdot 2^k > 2 \cdot 2^k$ (because $2^k > 0$ ),

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

Together: $3^{k + 1} > 1 + 2^{k + 1}$ , so $P(k + 1)$ is true. With the basis $P(2)$ : $9 > 5$ , the Extended Principle with $M = 2$ proves the conjecture.

Problem 4 · Which Conclusion Is Proved?

Given: $P(n)$ : $2^n > n^2$ . Scratch work shows: if $2^k > k^2$ , then $2^{k + 1} = 2 \cdot 2^k > 2k^2$ , and $2k^2 \ge (k + 1)^2$ for every natural number $k \ge 3$ . So $P(k) \to P(k + 1)$ is proved for every $k \ge 3$ . Also $P(1)$ is true ( $2 > 1$ ). Which conclusion does the Extended Principle justify?

✅ Correct!

P(5)

is true (

32 > 25

) and

5 \ge 3

, so the step holds for every

k \ge 5

❌ Not quite. The step is proved only for

k \ge 3

, so

P(1)

cannot start the chain; in fact

P(2)

is false (

4 > 4

fails).

❌ Not quite. The step holds from

3

on, but the basis

P(3)

is false:

2^3 = 8 < 9 = 3^2

❌ Not quite. The basis

P(4)

is false:

2^4 = 16 = 4^2

, and

16 > 16

fails.

Show solution

The Extended Principle needs a true basis $P(M)$ and the inductive step for every $k \ge M$ . The step is available for $k \ge 3$ , so $M \ge 3$ . Check the candidates:

$P(3)$ : $8 > 9$ is false.
$P(4)$ : $16 > 16$ is false.
$P(5)$ : $32 > 25$ is true.

With $M = 5$ : the basis holds, and every $k \ge 5$ satisfies $k \ge 3$ , so the step holds. Conclusion: $2^n > n^2$ for every $n \in \mathbb{N}$ with $n \ge 5$ . The true case $P(1)$ is not covered by this proof; it is checked separately.

Solved: 0 / 4

Extended Induction: Start the Basis Step at Any Integer M

IKey Formulas

IIVisualization 1 — Knock Over Domino MMM

IIIVisualization 2 — Where k≥4k \ge 4k≥4 Enters the Step

IVVisualization 3 — Find the Starting Value MMM

VQuiz Questions

IIVisualization 1 — Knock Over Domino $M$

IIIVisualization 2 — Where $k \ge 4$ Enters the Step

IVVisualization 3 — Find the Starting Value $M$