F(n)= F(n-1) + F(n-2) - Walk The Math

F_n= F_n-1 + F_n-2: a different perspective

The following observations were made when I set about to explore Fibonacci numbers. I made one mistake in my exploration. I assumed F₀=1.

The exploration started with the well-known recurrence equation: F_n = F_n-1 + F_n-2 (for n ≥ 2).

The fibonacci numbers Fib_n (F_n with F₀=0 & F₁=1) table look like this:

Fib₀	Fib₁	Fib₂	Fib₃	Fib₄	Fib₅	Fib₆	Fib₇	Fib₈	Fib₉	Fib₁₀	Fib₁₁
0	1	1	2	3	5	8	13	21	34	55	89

The series G_n (F_n with F₀=1 & F₁=1), that I ended up exploring, looks like this:

G₀	G₁	G₂	G₃	G₄	G₅	G₆	G₇	G₈	G₉	G₁₀	G₁₁
1	1	2	3	5	8	13	21	34	55	89	144

Observation 1: The relationship between Fib_n and G_n is given by: Fib_n = G_n+1 - G_n

Fib₁ = 1 & Fib₀ = 0
Fib₂ = Fib₁ + Fib₀ = Fib₁
Fib₃ = Fib₂ + Fib₁ = Fib₁ + Fib₁
Fib₄ = Fib₃ + Fib₂ = Fib₁ + Fib₁ + Fib₁
Fib₅ = Fib₄ + Fib₃ = Fib₁ + Fib₁ + Fib₁ + Fib₁ + Fib₁

G₁ = 1 & G₀ = 1
G₂ = G₁ + G₀
G₃ = G₂ + G₁ = G₁ + G₀ + G₁
G₄ = G₃ + G₂ = G₁ + G₀ + G₁ + G₁ + G₀
G₅ = G₄ + G₃ = G₁ + G₀ + G₁ + G₁ + G₀ + G₁ + G₀ + G₁

Observation 2:

G_n has G_n-1 G₁'s and G_n-2 G₀'s.
Fib_n has Fib_n-1 Fib₁'s and Fib_n-2 Fib₁'s.

Given an integer n, let R_n be the number of ways n can be reduced (by repeated use of factors 1 or 2) down to 1 or 0. Let P_n be the set of such paths from n to 1 or 0
The following tables lists the number of ways for n (in {2, 3, 4, 5}) to be reduced to 1 or 0:

For n=5	For n=4	For n=3	For n=2
P₅ 5 →_-1 4 →_-1 3 →_-1 2 →_-1 1 5 →_-1 4 →_-1 3 →_-1 2 →_-2 0 5 →_-1 4 →_-1 3 →_-2 1 5 →_-1 4 →_-2 2 →_-1 1 5 →_-1 4 →_-2 2 →_-2 0 5 →_-2 3 →_-1 2 →_-1 1 5 →_-2 3 →_-1 2 →_-2 0 5 →_-2 3 →_-2 1	P₄ 4 →_-1 3 →_-1 2 →_-1 1 4 →_-1 3 →_-1 2 →_-2 0 4 →_-1 3 →_-2 1 4 →_-2 2 →_-1 1 4 →_-2 2 →_-2 0	P₃ 3 →_-1 2 →_-1 1 3 →_-1 2 →_-2 0 3 →_-2 1	P₂ 2 →_-1 1 2 →_-2 0
Ways to reach 1 = 5 Ways to reach 0 = 3 Ways to reach 1 or 0 (R₅) = 8	Ways to reach 1 = 3 Ways to reach 0 = 2 Ways to reach 1 or 0 (R₄) = 5	Ways to reach 1 = 2 Ways to reach 0 = 1 Ways to reach 1 or 0 (R₃ ) = 3	Ways to reach 1 = 1 Ways to reach 0 = 1 Ways to 1 or 0 (R₂) = 2

Observation 3: R_n seems to be sum of R_n-1 and R_n-2 (with n ≥ 2 and R₁ and R₀ both taken to be 1).

Follows an informal reasoning to support the above observation. Suppose R_n is the number of ways 1 or 0 can be reached using reduction steps 1 or 2 and R_n-1 is the number of ways 1 or 0 can be reached similarly. Then to calculate R_n+1, since n is reachable from n+1 by only one possible path (a reduction step of 1) and n-2 is reachable by only one possible (a reduction step of 2), R_n+1 must be the total of R_n-1 and R_n.

Observation 4: The set P_n has exactly P_n-1 paths to reach 1 and P_n-2 paths to reach 0 (for n ≥ 2).

Observation 5: ∀ n . R_n = G_n (G_n = F_n = F_n-1+ F_n-2 n ≥ 2 with F₀ = F₁ = 1)

Using the above observations, Fib_n can be considered as the number of ways a given integer n can be reduced (by steps of 1 or 0) to 1.

Fn= Fn-1 + Fn-2: a different perspective

F_n= F_n-1 + F_n-2: a different perspective