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

Defining Sequences by Recursion: From Halving to n!

IKey Formulas

Definition	Formula	What it gives
Explicit formula	$a_n = \dfrac{1}{n}$	Any term directly: $a_{100} = \dfrac{1}{100}$
Recursive definition	$b_1 = 16$ , and $b_{n+1} = \tfrac{1}{2} b_n$ for $n \in \mathbb{N}$	Initial condition, then a recurrence relation that uses only earlier terms
Two general patterns ( $a, r \in \mathbb{R}$ )	$a_{n+1} = r \cdot a_n$ and $S_{n+1} = a + r \cdot S_n$ , with $a_1 = S_1 = a$	Conjectures: $a_n = a r^{n-1}$ and $S_n = a + ar + \cdots + ar^{n-1}$
A recursion for factorials	$a_0 = 1$ , and $a_{n+1} = (n+1) \cdot a_n$ for $n \in \mathbb{N} \cup \{0\}$	Proved by induction: $a_n = n!$ for every $n \ge 0$

Key Insight: A recursive definition has the shape of an induction proof: the initial condition is the first step, and the recurrence relation goes from each term to the next. Computed terms suggest a pattern; only a proof establishes it for every $n$ .

IIHalving, and the Gap Below 32

With $T_1 = 16$ and $T_{n+1} = 16 + \tfrac{1}{2} T_n$ , the distance $32 - T_n$ equals the halving term $b_n$ in every column computed.

Terms computed n 3

💡 Ten computed terms only suggest that $T_n$ approaches $32$ . What is proved here, by induction, is that every $b_n$ is positive: $b_1 > 0$ , and $b_n > 0$ gives $b_{n+1} = \tfrac{1}{2} b_n > 0$ .

IIITwo Patterns, One Recurrence Each

For any $a$ and $r$ , the terms computed from each recurrence agree with the conjectured formula in every row checked.

Pattern a 16 r 1/2

💡 Six agreeing rows are evidence for $n \le 6$ only. The last video of this unit proves both formulas by induction.

IVA Chain From $a_0$ to $a_{20}$

The initial condition gives $a_0$ , and each use of $a_{k+1} = (k+1) \cdot a_k$ gives the next term, which equals $(k+1)!$ .

Term n 6

VQuiz Questions

Problem 1 · Compute From the Recurrence

Given: $c_1 = 3$ , and for each $n \in \mathbb{N}$ , $c_{n+1} = 2c_n - 1$ . Find $c_4$ .

✅ Correct!

c_2 = 5

c_3 = 9

c_4 = 2 \cdot 9 - 1 = 17

❌ Not quite.

9

c_3

. Starting from

c_1 = 3

, reaching

c_4

takes three uses of the recurrence, not two.

❌ Not quite. That reads the rule as

2(c_n - 1)

, giving

4, 6, 10

. The recurrence doubles first and then subtracts

1

2c_n - 1

❌ Not quite.

33

c_5 = 2 \cdot 17 - 1

: one use of the recurrence too many.

Show solution

Apply the recurrence relation with $n = 1, 2, 3$ in turn; each step uses only the term before it.

c_2 = 2c_1 - 1 = 2 \cdot 3 - 1 = 5

c_3 = 2c_2 - 1 = 2 \cdot 5 - 1 = 9

c_4 = 2c_3 - 1 = 2 \cdot 9 - 1 = 17

So $c_4 = 17$ .

Problem 2 · A Recurrence That Uses the Index

Given: $e_1 = 2$ , and for each $n \in \mathbb{N}$ , $e_{n+1} = e_n + 2n$ . The first three terms are $2, 4, 8$ . Find $e_4$ .

✅ Correct!

e_4 = e_3 + 2 \cdot 3 = 8 + 6 = 14

. The first three terms looked like doubling, but the recurrence decides the next term, not the pattern.

❌ Not quite.

2, 4, 8

suggests doubling, but a guessed pattern is not the definition. The recurrence with

n = 3

gives

e_4 = e_3 + 2 \cdot 3

❌ Not quite. That adds

2(n+1)

at each step, giving

e_2 = 6

, which already disagrees with the given

e_2 = 4

. To get

e_{n+1}

, add

2n

, where

n

is the index of the term you start from.

❌ Not quite. That adds

2 \cdot 2

e_3

. Going from

e_3

e_4

uses

n = 3

, so the increase is

2 \cdot 3 = 6

Show solution

The recurrence with $n = 1$ , $n = 2$ and $n = 3$ :

e_2 = e_1 + 2 \cdot 1 = 2 + 2 = 4

e_3 = e_2 + 2 \cdot 2 = 4 + 4 = 8

e_4 = e_3 + 2 \cdot 3 = 8 + 6 = 14

The increases are $2, 4, 6, \ldots$ , not a doubling. Three terms that fit the guess $2^n$ were evidence for that guess, and the fourth term refutes it.

Problem 3 · The Second Pattern With $a = 5$ , $r = 3$

Given: $S_1 = 5$ , and for each $n \in \mathbb{N}$ , $S_{n+1} = 5 + 3S_n$ . Find $S_4$ , and check it against the conjecture $S_n = a + ar + \cdots + ar^{n-1}$ .

✅ Correct! The recurrence gives

20, 65, 200

, and the conjectured sum gives

5 + 15 + 45 + 135 = 200

as well.

❌ Not quite.

135 = 5 \cdot 3^3

is the fourth term of the first pattern,

a_4 = ar^3

S_4

is the sum of the first four of those terms.

❌ Not quite.

65

S_3

. One more use of the recurrence gives

S_4 = 5 + 3 \cdot 65

❌ Not quite.

605 = 5 + 3 \cdot 200

S_5

: one use of the recurrence too many.

Show solution

From the recurrence:

S_2 = 5 + 3 \cdot 5 = 20, \qquad S_3 = 5 + 3 \cdot 20 = 65, \qquad S_4 = 5 + 3 \cdot 65 = 200

From the conjecture with $a = 5$ , $r = 3$ , $n = 4$ :

S_4 = 5 + 5 \cdot 3 + 5 \cdot 3^2 + 5 \cdot 3^3 = 5 + 15 + 45 + 135 = 200

The two agree, so this case supports the conjecture. It is still one checked case, not a proof.

Problem 4 · Guess, Then Prove

Given: $c_0 = 1$ , and for each $n \in \mathbb{N} \cup \{0\}$ , $c_{n+1} = 2(n+1) \cdot c_n$ . Which explicit formula holds for every $n \ge 0$ ?

✅ Correct! The terms are

1, 2, 8, 48, 384

, which match

2^n \cdot n!

, and an induction with basis

n = 0

proves it for every

n \ge 0

❌ Not quite. It fits

c_0 = 1

and

c_1 = 2

, but

c_2 = 2 \cdot 2 \cdot c_1 = 8

, while

3! = 6

❌ Not quite. It fits

c_0 = 1

and

c_1 = 2

, but

c_2 = 8

, while

4! = 24

. Two agreeing terms were not enough.

❌ Not quite. It fails the initial condition:

2 \cdot 0! = 2

, but

c_0 = 1

Show solution

Compute terms. $c_1 = 2 \cdot 1 \cdot 1 = 2$ , $c_2 = 2 \cdot 2 \cdot 2 = 8$ , $c_3 = 2 \cdot 3 \cdot 8 = 48$ , $c_4 = 2 \cdot 4 \cdot 48 = 384$ . Compare $2^n \cdot n!$ : $1, 2, 8, 48, 384$ .

Prove $c_n = 2^n \cdot n!$ for each $n \in \mathbb{N} \cup \{0\}$ by the Extended Principle of Mathematical Induction with $M = 0$ .

Basis: $c_0 = 1$ and $2^0 \cdot 0! = 1 \cdot 1 = 1$ .

Inductive step: let $k \ge 0$ and assume $c_k = 2^k \cdot k!$ . By the recurrence with $n = k$ and then the assumption,

c_{k+1} = 2(k+1) \cdot c_k = 2(k+1) \cdot 2^k \cdot k! = 2^{k+1} \cdot (k+1) \cdot k! = 2^{k+1} \cdot (k+1)!

using $(k+1) \cdot k! = (k+1)!$ . By the Extended Principle, $c_n = 2^n \cdot n!$ for every $n \ge 0$ .

Solved: 0 / 4

Defining Sequences by Recursion: From Halving to n!

IKey Formulas

IIHalving, and the Gap Below 32

IIITwo Patterns, One Recurrence Each

IVA Chain From a0a_0a0​ to a20a_{20}a20​

VQuiz Questions

IVA Chain From $a_0$ to $a_{20}$