The Central Idea
The Fibonacci recurrence is
\[ \boxed{F_n=F_{n-1}+F_{n-2}}. \]Each new term is the sum of the two preceding terms.
With the initial conditions
\[ F_0=0,\qquad F_1=1, \]we obtain
\[ \boxed{0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ldots}. \]The recurrence supplies the rule; the initial conditions select the particular sequence.
The Classical Fibonacci Sequence
One common indexing convention defines
\[ F_0=0,\qquad F_1=1, \]with
\[ F_n=F_{n-1}+F_{n-2}\qquad(n\ge2). \]Then
\[ F_2=1, \] \[ F_3=2, \] \[ F_4=3, \] \[ F_5=5. \]Therefore,
\[ \boxed{0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ldots}. \]Another Common Indexing Convention
Some texts instead begin with
\[ F_1=1,\qquad F_2=1. \]Then
\[ F_3=2,\qquad F_4=3,\qquad F_5=5. \]The listed positive terms are the same:
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]but the subscripts are shifted.
Always check the indexing convention before using a Fibonacci formula or identity.
Why Two Initial Values Are Required
The recurrence
\[ a_n=a_{n-1}+a_{n-2} \]is second order.
To compute the first new term, we need two already-known values.
For example, to calculate
\[ a_3, \]we need
\[ a_2 \]and
\[ a_1. \]Therefore, two initial conditions are needed to determine a unique Fibonacci-type sequence.
What Makes a Sequence Fibonacci-Type?
A sequence is Fibonacci-type when it follows the same two-term addition rule
\[ \boxed{a_n=a_{n-1}+a_{n-2}} \]but may begin with initial values different from the classical Fibonacci sequence.
For example,
\[ a_1=2,\qquad a_2=3 \]gives
\[ \boxed{2,\ 3,\ 5,\ 8,\ 13,\ 21,\ldots}. \]Example: Different Initial Conditions
Let
\[ a_1=4,\qquad a_2=7, \] \[ a_n=a_{n-1}+a_{n-2}\qquad(n\ge3). \]Then
\[ a_3=7+4=11, \] \[ a_4=11+7=18, \] \[ a_5=18+11=29. \]Therefore,
\[ \boxed{4,\ 7,\ 11,\ 18,\ 29,\ldots}. \]Changing Initial Conditions Changes the Whole Sequence
Compare
\[ a_1=1,\qquad a_2=1 \]with
\[ b_1=2,\qquad b_2=5. \]Under the same recurrence
\[ x_n=x_{n-1}+x_{n-2}, \]the first sequence is
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]while the second is
\[ 2,\ 5,\ 7,\ 12,\ 19,\ 31,\ldots \]The recursive structure is identical, but the starting state is different.
Lucas-Type Example
A famous Fibonacci-type sequence begins
\[ L_0=2,\qquad L_1=1 \]and uses
\[ L_n=L_{n-1}+L_{n-2}. \]Then
\[ L_2=3,\qquad L_3=4,\qquad L_4=7,\qquad L_5=11. \]Thus,
\[ \boxed{2,\ 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ldots}. \]This is called the Lucas sequence.
Fibonacci-Type Sequences Are Linear Recurrences
The recurrence
\[ a_n=a_{n-1}+a_{n-2} \]is:
- linear;
- second order;
- constant coefficient;
- homogeneous.
Its coefficients are
\[ \boxed{1\text{ and }1}. \]Forward Evaluation
Fibonacci-type sequences are naturally generated forward.
Suppose
\[ a_1=3,\qquad a_2=4. \]Then
\[ a_3=4+3=7, \] \[ a_4=7+4=11, \] \[ a_5=11+7=18, \] \[ a_6=18+11=29. \]At each step, the two most recent terms are sufficient to continue.
The State Pair
Because two previous terms determine the next term, a convenient state is the ordered pair
\[ \boxed{(a_{n-1},a_n)}. \]Under the Fibonacci recurrence, the transition is
\[ (a_{n-1},a_n) \longrightarrow (a_n,a_{n-1}+a_n). \]The first component shifts forward, and the second component becomes the new sum.
Example: State Transitions
Start with
\[ (2,5). \]Then
\[ (2,5)\longrightarrow(5,7), \] \[ (5,7)\longrightarrow(7,12), \] \[ (7,12)\longrightarrow(12,19). \]The corresponding sequence is
\[ \boxed{2,\ 5,\ 7,\ 12,\ 19,\ldots}. \]Scaling a Fibonacci-Type Sequence
Suppose \(a_n\) satisfies
\[ a_n=a_{n-1}+a_{n-2}. \]If every term is multiplied by a constant \(c\), then
\[ b_n=ca_n \]also satisfies the same recurrence:
\[ b_n = c(a_{n-1}+a_{n-2}) = ca_{n-1}+ca_{n-2} = b_{n-1}+b_{n-2}. \]This is an example of linearity and superposition.
Example: A Scaled Fibonacci Sequence
Starting with the classical positive-index Fibonacci sequence
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]multiply every term by \(4\):
\[ \boxed{4,\ 4,\ 8,\ 12,\ 20,\ 32,\ldots}. \]The new sequence still satisfies
\[ a_n=a_{n-1}+a_{n-2}. \]Adding Fibonacci-Type Sequences
Suppose \(a_n\) and \(b_n\) both satisfy
\[ x_n=x_{n-1}+x_{n-2}. \]Define
\[ c_n=a_n+b_n. \]Then
\[ c_n = a_n+b_n = (a_{n-1}+a_{n-2})+(b_{n-1}+b_{n-2}). \]Regrouping gives
\[ c_n=c_{n-1}+c_{n-2}. \]Therefore, the sum is also Fibonacci-type.
Every Initial Pair Determines a Fibonacci-Type Sequence
Let
\[ a_0=p,\qquad a_1=q. \]Then the recurrence determines
\[ a_2=p+q, \] \[ a_3=q+(p+q)=p+2q, \] \[ a_4=(p+q)+(p+2q)=2p+3q. \]Thus, the entire sequence is determined by the initial pair \((p,q)\).
Early Terms in Terms of the Initial Conditions
Starting with
\[ a_0=p,\qquad a_1=q, \]we obtain
\[ a_2=p+q, \] \[ a_3=p+2q, \] \[ a_4=2p+3q, \] \[ a_5=3p+5q. \]Notice that the coefficients themselves follow Fibonacci-like patterns.
Fibonacci Numbers Reappear as Coefficients
For \(n\ge1\), a Fibonacci-type sequence with
\[ a_0=p,\qquad a_1=q \]can be expressed in terms of classical Fibonacci numbers as
\[ \boxed{a_n=F_{n-1}p+F_nq}. \]For example, when \(n=5\),
\[ a_5=F_4p+F_5q=3p+5q. \]This formula shows how the initial data propagates through the recurrence.
Shifted Fibonacci Sequences
A sequence can begin later in the Fibonacci list and still satisfy the same recurrence.
For example,
\[ 3,\ 5,\ 8,\ 13,\ 21,\ldots \]is simply a shifted portion of the Fibonacci sequence.
It satisfies
\[ a_1=3,\qquad a_2=5,\qquad a_n=a_{n-1}+a_{n-2}. \]Negative Initial Values
Fibonacci-type recurrences do not require positive starting values.
Suppose
\[ a_1=-2,\qquad a_2=5. \]Then
\[ a_3=3, \] \[ a_4=8, \] \[ a_5=11, \] \[ a_6=19. \]Therefore,
\[ \boxed{-2,\ 5,\ 3,\ 8,\ 11,\ 19,\ldots}. \]Zero Initial Values
Suppose
\[ a_1=0,\qquad a_2=0. \]Then every later term is also zero:
\[ a_3=0+0=0, \] \[ a_4=0+0=0. \]Thus,
\[ \boxed{0,\ 0,\ 0,\ 0,\ldots}. \]This is the trivial solution of the homogeneous recurrence.
One Zero Initial Value
Suppose
\[ a_0=0,\qquad a_1=c. \]Then
\[ a_2=c, \] \[ a_3=2c, \] \[ a_4=3c, \] \[ a_5=5c. \]Therefore,
\[ \boxed{a_n=cF_n}. \]The classical Fibonacci sequence is the case \(c=1\).
Ratios of Consecutive Fibonacci Terms
Consider the ratios
\[ \frac{F_2}{F_1}=1, \] \[ \frac{F_3}{F_2}=2, \] \[ \frac{F_4}{F_3}=\frac32, \] \[ \frac{F_5}{F_4}=\frac53, \] \[ \frac{F_6}{F_5}=\frac85. \]These ratios do not remain constant, so the Fibonacci sequence is not geometric.
However, the ratios approach a particular limiting value, developed later when closed forms and characteristic methods are introduced.
Fibonacci Is Neither Arithmetic nor Geometric
The Fibonacci sequence
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]does not have a constant difference:
\[ 0,\ 1,\ 1,\ 2,\ 3,\ldots \]and it does not have a constant ratio.
Its structure comes from a second-order recurrence rather than repeated addition of one constant or multiplication by one constant.
A Useful Sum Identity
The first several Fibonacci numbers satisfy
\[ F_0+F_1+\cdots+F_n=F_{n+2}-1. \]For example, with \(n=5\),
\[ 0+1+1+2+3+5=12 \]and
\[ F_7-1=13-1=12. \]Thus,
\[ \boxed{\sum_{k=0}^{n}F_k=F_{n+2}-1}. \]Why the Sum Identity Is Plausible
The recurrence
\[ F_{k+2}=F_{k+1}+F_k \]can be rearranged as
\[ F_k=F_{k+2}-F_{k+1}. \]Summing these differences creates extensive cancellation:
\[ (F_2-F_1)+(F_3-F_2)+\cdots+(F_{n+2}-F_{n+1}). \]Most intermediate terms cancel, leaving
\[ F_{n+2}-F_1. \]Since \(F_1=1\), the result is
\[ F_{n+2}-1. \]A Consecutive-Term Identity
Another useful identity is
\[ \boxed{F_{n+1}=F_n+F_{n-1}}. \]This is simply the defining recurrence written one index later.
Many Fibonacci identities can be understood as repeated consequences of the recurrence itself.
Odd-Index and Even-Index Patterns
Fibonacci numbers exhibit many secondary patterns.
For example, every third Fibonacci number is even:
\[ F_0=0,\qquad F_3=2,\qquad F_6=8,\qquad F_9=34,\ldots \]Such regularities arise because recursive sequences often carry modular patterns from one state to the next.
Parity Pattern
Reduce the Fibonacci recurrence modulo \(2\).
Starting with
\[ 0,\ 1, \]the parity pattern becomes
\[ 0,\ 1,\ 1,\ 0,\ 1,\ 1,\ 0,\ldots \]and repeats with period \(3\).
This explains why every third Fibonacci number is even.
Recursive Sequences Can Reveal Modular Cycles
Because a second-order recurrence is determined by the current pair
\[ (a_{n-1},a_n), \]reducing terms modulo \(m\) leaves only finitely many possible state pairs.
Repeated states can therefore create cycles in the modular behavior.
This is a useful example of how finite state spaces interact with recursive sequences.
Fibonacci Numbers and Counting
Fibonacci numbers arise naturally in counting problems where an object can be built from pieces of two allowed sizes.
A common example asks for the number of ways to cover a strip of length \(n\) using pieces of lengths \(1\) and \(2\).
If \(T_n\) counts such coverings, then the final piece is either:
- a length-\(1\) piece, leaving a problem of size \(n-1\); or
- a length-\(2\) piece, leaving a problem of size \(n-2\).
Therefore,
\[ \boxed{T_n=T_{n-1}+T_{n-2}}. \]Example: Tiling a Short Board
Let \(T_n\) be the number of ways to tile a length-\(n\) board using length-\(1\) squares and length-\(2\) dominoes.
For \(n=1\),
\[ T_1=1. \]For \(n=2\),
\[ T_2=2. \]Therefore,
\[ T_3=T_2+T_1=3, \] \[ T_4=T_3+T_2=5. \]Thus,
\[ \boxed{1,\ 2,\ 3,\ 5,\ 8,\ldots}. \]Why the Counting Recurrence Works
Every valid tiling of a length-\(n\) board ends in exactly one of two ways.
If it ends with a square, removing that square leaves any valid tiling of length \(n-1\).
If it ends with a domino, removing that domino leaves any valid tiling of length \(n-2\).
These cases are disjoint and exhaustive, so their counts add.
\[ \boxed{T_n=T_{n-1}+T_{n-2}}. \]Example: Stair-Step Counting
Suppose a person can climb either \(1\) stair or \(2\) stairs at a time.
Let \(S_n\) be the number of ways to reach stair \(n\).
Every route to stair \(n\) must arrive from either:
\[ n-1 \]or
\[ n-2. \]Therefore,
\[ \boxed{S_n=S_{n-1}+S_{n-2}}. \]Again, Fibonacci-type structure appears through a two-case decomposition.
Fibonacci-Type Recurrences in Population Models
Historically, Fibonacci numbers are associated with an idealized population model in which new reproduction depends on age classes.
The exact historical model is highly simplified, but its mathematical value lies in demonstrating how a current population count can depend on multiple earlier states.
This is a general feature of delayed or age-structured discrete models.
Recursive Growth Is Not Constant-Rate Growth
Fibonacci growth does not add the same amount each step.
It also does not multiply by exactly the same factor each step.
Instead, the amount of change itself depends on earlier values:
\[ a_n-a_{n-1}=a_{n-2}. \]Thus, the first difference of a Fibonacci-type sequence is itself a shifted version of the sequence.
Difference Structure
From
\[ a_n=a_{n-1}+a_{n-2}, \]subtract \(a_{n-1}\):
\[ \boxed{a_n-a_{n-1}=a_{n-2}}. \]This equation describes the change between consecutive terms.
Unlike an arithmetic sequence, the change is not constant; it evolves according to the sequence itself.
Recovering Earlier Terms
The Fibonacci recurrence can be rearranged:
\[ a_n=a_{n-1}+a_{n-2}. \]Therefore,
\[ \boxed{a_{n-2}=a_n-a_{n-1}}. \]If two consecutive terms are known, we can step backward as well as forward.
Example: Recover Terms Backward
Suppose two consecutive terms are
\[ a_5=18,\qquad a_6=29. \]Then
\[ a_4=29-18=11. \]Next,
\[ a_3=18-11=7. \]Then
\[ a_2=11-7=4. \]The sequence is therefore
\[ \boxed{4,\ 7,\ 11,\ 18,\ 29,\ldots}. \]Extending Fibonacci Numbers to Negative Indices
Because the recurrence can be run backward, the classical Fibonacci sequence can be extended to negative indices.
From
\[ F_1=F_0+F_{-1}, \]with \(F_1=1\) and \(F_0=0\), we get
\[ F_{-1}=1. \]Continuing backward yields alternating signs.
This extension is mathematically useful, though positive and zero indices remain the main focus here.
Closed Forms Exist, but Recursion Comes First
The Fibonacci recurrence has a famous explicit formula involving powers of two algebraic numbers.
That formula is important because it converts the recursive definition into direct term evaluation.
However, deriving it properly requires methods developed later in this chapter.
For now, the main goal is understanding the recursive structure and how initial conditions propagate.
Common Error: Using Only One Initial Value
The recurrence
\[ a_n=a_{n-1}+a_{n-2} \]is second order.
A single initial value does not determine the next term.
Two starting values are normally required.
Common Error: Adding the Wrong Terms
To calculate \(a_n\), use
\[ a_{n-1} \]and
\[ a_{n-2}. \]For example, \(a_8\) depends on \(a_7\) and \(a_6\), not \(a_7\) and \(a_5\).
Common Error: Mixing Indexing Conventions
The conventions
\[ F_0=0,\quad F_1=1 \]and
\[ F_1=1,\quad F_2=1 \]describe the same familiar positive values but assign different subscripts near the beginning.
Identities and formulas must be used with the convention for which they were stated.
Common Error: Assuming Fibonacci-Type Means Classical Fibonacci
The sequence
\[ 4,\ 7,\ 11,\ 18,\ 29,\ldots \]is Fibonacci-type because each term is the sum of the previous two.
It is not the classical Fibonacci sequence because its initial conditions are different.
Common Error: Treating the Sequence as Geometric
Fibonacci ratios approach a limiting value, but the consecutive ratios are not exactly constant.
Therefore, Fibonacci-type sequences are not generally geometric.
Their defining structure is second-order recursion.
Common Error: Looking for a Fixed Difference
In
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]the differences are
\[ 0,\ 1,\ 1,\ 2,\ 3,\ldots \]and are not constant.
The change at each step is itself determined recursively.
Common Error: Guessing a Closed Form Too Early
A recursive sequence can be perfectly well defined even when no explicit formula has yet been found.
Forward computation, induction, combinatorial reasoning, and modular analysis can all be performed directly from the recurrence.
Closed forms are useful tools, not prerequisites for understanding the sequence.
A Reliable Procedure for Generating Fibonacci-Type Terms
- Identify the two initial values.
- Check the starting indices.
- Identify the first index at which the recurrence applies.
- Add the two immediately preceding terms.
- Record the new term in the correct position.
- Repeat using the newest two consecutive terms.
- Check arithmetic and indexing at each step.
A Reliable Procedure for Recognizing Fibonacci-Type Structure
- Check whether each term after the initial pair equals the sum of the two preceding terms.
- Verify the pattern for several consecutive positions.
- State the initial values explicitly.
- Write the recurrence with its valid index range.
A complete recursive definition needs both the recurrence and the initial data.
A Reliable Procedure for Counting with Fibonacci Recursion
- Identify the size-\(n\) objects being counted.
- Partition them into disjoint cases based on a final or first structural choice.
- Show that one case reduces to a size-\(n-1\) problem.
- Show that another case reduces to a size-\(n-2\) problem.
- Add the case counts.
- Determine the necessary initial counts.
This yields a recurrence of the form
\[ T_n=T_{n-1}+T_{n-2}. \]Practice 1: Classical Fibonacci Terms
Let
\[ F_0=0,\qquad F_1=1, \] \[ F_n=F_{n-1}+F_{n-2}. \]Find \(F_2,F_3,F_4,F_5,F_6\).
Practice 2: Fibonacci-Type Sequence
Let
\[ a_1=3,\qquad a_2=8, \] \[ a_n=a_{n-1}+a_{n-2}. \]Find the next five terms.
Practice 3: Negative Initial Value
Let
\[ a_1=-1,\qquad a_2=4. \]Generate \(a_3,a_4,a_5,a_6\).
Practice 4: Recover Earlier Terms
A Fibonacci-type sequence has
\[ a_5=13,\qquad a_6=21. \]Find \(a_4,a_3,a_2\).
Practice 5: Determine Whether a Sequence Is Fibonacci-Type
Determine whether
\[ 2,\ 4,\ 6,\ 10,\ 16,\ 26,\ldots \]follows the Fibonacci-type recurrence.
Practice 6: Scale a Sequence
The sequence
\[ 1,\ 1,\ 2,\ 3,\ 5,\ldots \]satisfies the Fibonacci recurrence.
Multiply every term by \(6\) and verify that the resulting first five terms still satisfy the same recurrence.
Practice 7: Initial Pair Formula
Suppose
\[ a_0=p,\qquad a_1=q \]and
\[ a_n=a_{n-1}+a_{n-2}. \]Express \(a_2,a_3,a_4\) in terms of \(p\) and \(q\).
Practice 8: Tiling Recurrence
A length-\(n\) strip is tiled with pieces of length \(1\) or \(2\).
Explain why the number \(T_n\) of tilings satisfies
\[ T_n=T_{n-1}+T_{n-2}. \]Practice 9: Fibonacci Sum
Using
\[ F_0=0,\ F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8, \]verify
\[ F_0+F_1+\cdots+F_4=F_6-1. \]Practice 10: Classify the Recurrence
Classify
\[ a_n=a_{n-1}+a_{n-2} \]by linearity, order, coefficient type, and homogeneity.
Practice Answers
Practice 1
\[ F_2=1, \] \[ F_3=2, \] \[ F_4=3, \] \[ F_5=5, \] \[ F_6=8. \]Therefore,
\[ \boxed{1,\ 2,\ 3,\ 5,\ 8}. \]Practice 2
\[ a_3=8+3=11, \] \[ a_4=11+8=19, \] \[ a_5=19+11=30, \] \[ a_6=30+19=49, \] \[ a_7=49+30=79. \]Therefore,
\[ \boxed{11,\ 19,\ 30,\ 49,\ 79}. \]Practice 3
\[ a_3=4+(-1)=3, \] \[ a_4=3+4=7, \] \[ a_5=7+3=10, \] \[ a_6=10+7=17. \]Therefore,
\[ \boxed{a_3=3,\quad a_4=7,\quad a_5=10,\quad a_6=17}. \]Practice 4
Work backward using
\[ a_{n-2}=a_n-a_{n-1}. \]Then
\[ a_4=21-13=8, \] \[ a_3=13-8=5, \] \[ a_2=8-5=3. \]Therefore,
\[ \boxed{a_4=8,\quad a_3=5,\quad a_2=3}. \]Practice 5
Check consecutive sums:
\[ 2+4=6, \] \[ 4+6=10, \] \[ 6+10=16, \] \[ 10+16=26. \]Therefore,
\[ \boxed{\text{Yes, the sequence is Fibonacci-type.}} \]Practice 6
Multiplying by \(6\) gives
\[ 6,\ 6,\ 12,\ 18,\ 30. \]Check:
\[ 6+6=12, \] \[ 6+12=18, \] \[ 12+18=30. \]Therefore, the scaled sequence still satisfies the recurrence.
Practice 7
\[ a_2=p+q, \] \[ a_3=q+(p+q)=p+2q, \] \[ a_4=(p+q)+(p+2q)=2p+3q. \]Therefore,
\[ \boxed{ a_2=p+q,\qquad a_3=p+2q,\qquad a_4=2p+3q }. \]Practice 8
Every tiling ends with either a length-\(1\) piece or a length-\(2\) piece.
Removing a final length-\(1\) piece leaves any tiling of length \(n-1\). Removing a final length-\(2\) piece leaves any tiling of length \(n-2\).
These cases are disjoint, so
\[ \boxed{T_n=T_{n-1}+T_{n-2}}. \]Practice 9
\[ F_0+F_1+F_2+F_3+F_4 = 0+1+1+2+3 = 7. \]Also,
\[ F_6-1=8-1=7. \]Therefore,
\[ \boxed{F_0+F_1+\cdots+F_4=F_6-1}. \]Practice 10
The recurrence is linear because the earlier terms form a linear combination.
It is second order because it reaches back to \(a_{n-2}\).
Its coefficients \(1\) and \(1\) are constant.
There is no forcing term.
\[ \boxed{\text{linear, second order, constant coefficient, homogeneous}} \]What to Remember
Fibonacci-type sequences are defined by the two-step recurrence
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]- Two initial values are required to determine a unique sequence.
- The classical Fibonacci sequence is only one choice of initial conditions.
- Different initial pairs produce different Fibonacci-type sequences.
- The recurrence is linear, second order, constant coefficient, and homogeneous.
- Scaling or adding solutions preserves the recurrence.
- The state can be represented by the pair \((a_{n-1},a_n)\).
- The recurrence can be run forward or backward.
- Fibonacci-type structures appear naturally in counting and state-transition problems.
- The sequence is generally neither arithmetic nor geometric.
- Closed forms exist for important cases, but recursive reasoning remains fundamental.
Where We Go Next
Fibonacci-type sequences show how a current term can depend on several earlier terms. Another useful way to study discrete change is to focus directly on the differences between successive states.
The next lesson, Difference Equations, develops equations written in terms of discrete changes, connects first differences with recurrence relations, and provides a discrete counterpart to continuous change equations.