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

Every Third Fibonacci Number Is Even: An Induction Proof

IKey Formulas

Statement	Formula
Fibonacci numbers	$f_1 = f_2 = 1$ , $\;f_{n+2} = f_{n+1} + f_n$ for $n \in \mathbb{N}$
The term $P(k+1)$ is about	$f_{3(k+1)} = f_{3k+3}$ , three places past $f_{3k}$
Recursion formula, applied twice	$f_{3k+3} = 2f_{3k+1} + f_{3k}$
Substitute $f_{3k} = 2m$	$f_{3(k+1)} = 2\left(f_{3k+1} + m\right)$

Key Insight: $P(k)$ says nothing about $f_{3k+1}$ or $f_{3k+2}$ , so the recursion formula must be applied twice until $f_{3k}$ appears; then the even term $2f_{3k+1}$ plus the even term $f_{3k}$ is even.

IIThree Places Along the Sequence

$P(k)$ is about $f_{3k}$ and $P(k+1)$ about $f_{3k+3}$ ; the two terms between them are odd.

k 2

IIIThe Recursion Formula, Twice

Two applications of $f_{n+2} = f_{n+1} + f_n$ express $f_{3(k+1)}$ through $f_{3k+1}$ and $f_{3k}$ .

Step 1 Check at

Index: 3(k + 1) = 3k + 3

f_{3(k+1)} = f_{3k+3}

Recursion formula with n = 3k + 1

\phantom{f_{3(k+1)}} = f_{3k+2} + f_{3k+1}

Recursion formula again, with n = 3k

\phantom{f_{3(k+1)}} = (f_{3k+1} + f_{3k}) + f_{3k+1}

The term f₃ₖ₊₁ appears twice

\phantom{f_{3(k+1)}} = 2f_{3k+1} + f_{3k}

Inductive hypothesis f₃ₖ = 2m, then factor out 2

\phantom{f_{3(k+1)}} = 2f_{3k+1} + 2m = 2(f_{3k+1} + m)

IVThe Know-Show Table, Filled

The table works from both ends: the hypothesis forward, the goal backward, until $q = f_{3k+1} + m$ joins them.

Step 1 Witnesses at

Step	Know	Reason
P	$f_{3k}$ is even.	Inductive hypothesis
P1	$(\exists m \in \mathbb{Z})\,(f_{3k} = 2m)$	Definition of even integer
P2	$f_{3(k+1)} = 2f_{3k+1} + f_{3k}$	Recursion formula, twice
P3	$f_{3(k+1)} = 2(f_{3k+1} + m)$	Substitute P1, factor
⋮	⋮	⋮
Q1	$(\exists q \in \mathbb{Z})\,(f_{3(k+1)} = 2q)$	P3, with $q = f_{3k+1} + m$
Q	$f_{3(k+1)}$ is even.	Definition of even integer
Step	Show	Reason

VQuiz Questions

Problem 1 · Which Term Is P(k+1) About?

Given: $P(n)$ : $f_{3n}$ is an even natural number. In the inductive step, $P(k+1)$ is a statement about which Fibonacci number?

✅ Correct! Replacing

n

k+1

gives the index

3(k+1) = 3k + 3

, three places past

f_{3k}

❌ Not quite.

f_{3k+1}

is the next term after

f_{3k}

; it comes from dropping the parentheses in

3(k+1)

. The index is

3(k+1) = 3k + 3

, not

3k + 1

❌ Not quite.

f_{3k} + 3

adds

3

to the value of a term.

P(k+1)

changes the index: it is about the term

f_{3(k+1)}

. With

k = 1

f_3 + 3 = 5

, but

f_6 = 8

❌ Not quite. The factor

3

in the index stays:

P(k+1)

replaces

n

k+1

f_{3n}

, giving

f_{3(k+1)}

, not

f_{k+1}

Show solution

$P(k+1)$ is obtained from $P(n)$ by replacing $n$ with $k+1$ :

P(k+1):\ f_{3(k+1)} \text{ is an even natural number.}

Since $3(k+1) = 3k + 3$ , this is a statement about $f_{3k+3}$ . For example, with $k = 3$ it is about $f_{12} = 144$ , while $P(3)$ is about $f_9 = 34$ .

Problem 2 · A Flawed Inductive Step

Given: A student writes: "Assume $f_{3k}$ is even. By the recursion formula $f_{3k+3} = f_{3k+2} + f_{3k+1}$ , and both terms on the right are even by the inductive hypothesis, so $f_{3k+3}$ is even." What is wrong?

✅ Correct!

P(k)

says nothing about

f_{3k+1}

f_{3k+2}

, and both are odd (for

k = 1

f_4 = 3

f_5 = 5

). Apply the recursion formula once more so that

f_{3k}

appears.

❌ Not quite. The step uses a claim the hypothesis never made. For

k = 1

the "even" terms are

f_5 = 5

and

f_4 = 3

, both odd; the conclusion

f_6 = 8

is even for a different reason.

❌ Not quite. The recursion formula applies with

n = 3k + 1

f_{3k+3} = f_{3k+2} + f_{3k+1}

is correct. The error is the claim that the two terms on the right are even.

❌ Not quite. Every

P(j)

is about an index that is a multiple of

3

, so even

P(1), \ldots, P(k)

together say nothing about

f_{3k+1}

f_{3k+2}

; those terms are odd anyway.

Show solution

The equation $f_{3k+3} = f_{3k+2} + f_{3k+1}$ is right, but the inductive hypothesis is only " $f_{3k}$ is even." Neither $f_{3k+2}$ nor $f_{3k+1}$ is $f_{3k}$ , and both are odd: $f_4 = 3$ , $f_5 = 5$ , $f_7 = 13$ , $f_8 = 21$ .

The fix is to apply the recursion formula again, to $f_{3k+2} = f_{3k+1} + f_{3k}$ :

f_{3k+3} = (f_{3k+1} + f_{3k}) + f_{3k+1} = 2f_{3k+1} + f_{3k}.

Now $2f_{3k+1}$ is even and $f_{3k}$ is even by the hypothesis, so the sum is even.

Problem 3 · Find the Witness q

Given: Take $k = 4$ , so the inductive hypothesis gives $f_{12} = 144 = 2m$ . The proof shows $f_{15} = 2q$ with $q = f_{3k+1} + m$ . What is $q$ ? (Use $f_{13} = 233$ and $f_{14} = 377$ .)

✅ Correct!

m = 72

and

q = f_{13} + m = 233 + 72 = 305

, so

f_{15} = 2 \cdot 305 = 610

❌ Not quite.

449 = f_{14} + m

uses

f_{3k+2}

. The witness uses

f_{3k+1} = f_{13} = 233

; check:

2 \cdot 449 = 898 \ne 610

❌ Not quite.

377 = f_{13} + f_{12}

adds

f_{3k}

instead of

m = f_{3k}/2 = 72

; check:

2 \cdot 377 = 754 \ne 610

❌ Not quite.

610

f_{15}

itself. The witness is the integer

q

with

f_{15} = 2q

, half of

610

Show solution

From $f_{12} = 144 = 2m$ we get $m = 72$ . With $k = 4$ , $f_{3k+1} = f_{13} = 233$ , so

q = f_{13} + m = 233 + 72 = 305.

Check against the identity: $f_{15} = 2f_{13} + f_{12} = 2 \cdot 233 + 144 = 610 = 2 \cdot 305$ , and indeed $f_{15} = f_{14} + f_{13} = 377 + 233 = 610$ .

Problem 4 · Every Fourth Fibonacci Number

Given: Claim: for each $n \in \mathbb{N}$ , $3 \mid f_{4n}$ . The basis is $f_4 = 3$ . In the inductive step the hypothesis is $f_{4k} = 3m$ for some integer $m$ . Which identity, from repeated use of the recursion formula, lets the inductive step use the hypothesis?

✅ Correct! Then

f_{4k+4} = 3f_{4k+1} + 2 \cdot 3m = 3(f_{4k+1} + 2m)

, a multiple of

3

. Check at

k = 1

f_8 = 21 = 3 \cdot 5 + 2 \cdot 3

❌ Not quite. That is the three-step identity with

3k

replaced by

4k

; four places need one more application of the recursion formula. At

k = 1

it gives

2 \cdot 5 + 3 = 13

, but

f_8 = 21

❌ Not quite. The coefficient of

f_{4k}

is off: at

k = 1

this gives

3 \cdot 5 + 3 = 18

, but

f_8 = 21

. Expanding

2f_{4k+2} + f_{4k+1}

with

f_{4k+2} = f_{4k+1} + f_{4k}

produces

2f_{4k}

❌ Not quite. The correct expansion at this stage is

2f_{4k+2} + f_{4k+1}

, not

+\,f_{4k}

. At

k = 1

this option gives

2 \cdot 8 + 3 = 19

, but

f_8 = 21

Show solution

Apply the recursion formula three times, each time to the highest-index term:

\begin{aligned} f_{4k+4} &= f_{4k+3} + f_{4k+2} = (f_{4k+2} + f_{4k+1}) + f_{4k+2} = 2f_{4k+2} + f_{4k+1} \\ &= 2(f_{4k+1} + f_{4k}) + f_{4k+1} = 3f_{4k+1} + 2f_{4k}. \end{aligned}

Substituting $f_{4k} = 3m$ :

f_{4(k+1)} = 3f_{4k+1} + 6m = 3(f_{4k+1} + 2m),

and $f_{4k+1} + 2m$ is an integer, so $3 \mid f_{4(k+1)}$ . Check: $k = 1$ gives $f_8 = 3 \cdot 5 + 2 \cdot 3 = 21$ ; $k = 2$ gives $f_{12} = 3 \cdot 34 + 2 \cdot 21 = 144$ .

Solved: 0 / 4