The Central Idea
The Fibonacci sequence begins
\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ldots \]Each term after the first two is the sum of the two terms before it:
\[ 2=1+1, \] \[ 3=2+1, \] \[ 5=3+2, \] \[ 8=5+3. \]The recursive rule is
\[ \boxed{ F_1=1,\qquad F_2=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\geq3) }. \]Because the recurrence depends on two previous terms, two starting values are required.
What Is a Fibonacci-Type Recurrence?
A Fibonacci-type recurrence is a recursive rule in which later terms are built from two or more earlier terms.
The simplest and most familiar form is
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]Different initial values produce different sequences even when the recurrence relation itself remains unchanged.
The Recurrence and the Initial Conditions
A complete second-order recurrence requires two pieces of starting data.
For example,
\[ a_1=2,\qquad a_2=5 \]together with
\[ a_n=a_{n-1}+a_{n-2} \]determine the sequence
\[ 2,\ 5,\ 7,\ 12,\ 19,\ 31,\ldots \]The recurrence describes the rule, while the initial conditions select the particular sequence.
Why Two Initial Values Are Needed
Suppose
\[ a_n=a_{n-1}+a_{n-2}. \]To find \(a_3\), we need both
\[ a_2 \]and
\[ a_1. \]If only one starting value is known, then the second starting value remains undetermined and many different sequences are possible.
Example: Generating Terms
Let
\[ a_1=3,\qquad a_2=4, \]and define
\[ a_n=a_{n-1}+a_{n-2}. \]Then
\[ a_3=4+3=7, \] \[ a_4=7+4=11, \] \[ a_5=11+7=18, \] \[ a_6=18+11=29. \]Therefore,
\[ \boxed{3,\ 4,\ 7,\ 11,\ 18,\ 29,\ldots}. \]The Classical Fibonacci Sequence
One common indexing convention defines the Fibonacci sequence by
\[ F_0=0,\qquad F_1=1 \]and
\[ F_n=F_{n-1}+F_{n-2}\qquad(n\geq2). \]This gives
\[ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ldots \]Another common convention begins with \(F_1=1\) and \(F_2=1\).
Both conventions describe the same familiar values with shifted indices.
Indexing Conventions Matter
Under the convention
\[ F_0=0,\qquad F_1=1, \]we have
\[ F_5=5. \]Under the convention
\[ F_1=1,\qquad F_2=1, \]we also encounter the same value pattern, but each term's index is shifted.
Always check the initial indexing before using a Fibonacci formula or table.
Second-Order Recurrences
A recurrence that depends on the two preceding terms is called a second-order recurrence.
A common general form is
\[ \boxed{ a_n=pa_{n-1}+qa_{n-2} }. \]Here, \(p\) and \(q\) are constants.
The Fibonacci recurrence is the special case
\[ p=1,\qquad q=1. \]Example: A Weighted Fibonacci-Type Recurrence
Let
\[ a_1=1,\qquad a_2=2, \]and define
\[ a_n=2a_{n-1}+a_{n-2}. \]Then
\[ a_3=2(2)+1=5, \] \[ a_4=2(5)+2=12, \] \[ a_5=2(12)+5=29. \]Thus,
\[ \boxed{1,\ 2,\ 5,\ 12,\ 29,\ldots}. \]Subtraction Can Appear Too
A second-order recurrence does not have to add both previous terms.
For example,
\[ a_n=2a_{n-1}-a_{n-2} \]is also a second-order linear recurrence.
If
\[ a_1=3,\qquad a_2=7, \]then
\[ a_3=2(7)-3=11, \] \[ a_4=2(11)-7=15, \] \[ a_5=2(15)-11=19. \]The resulting sequence is arithmetic:
\[ \boxed{3,\ 7,\ 11,\ 15,\ 19,\ldots}. \]One Sequence Can Have More Than One Description
The sequence
\[ 3,\ 7,\ 11,\ 15,\ldots \]can be defined arithmetically by
\[ a_n=a_{n-1}+4 \]or by the second-order recurrence
\[ a_n=2a_{n-1}-a_{n-2}. \]Different recursive rules can sometimes describe the same sequence.
The most useful description depends on which structure we want to expose.
A Recurrence as an Algorithm
A Fibonacci-type recurrence naturally becomes an algorithm.
For
\[ a_n=a_{n-1}+a_{n-2}, \]an iterative procedure is:
- store the two current terms;
- add them to obtain the next term;
- discard or move past the oldest term;
- shift the newer terms forward;
- repeat.
This is one of the simplest examples of maintaining computational state.
State in a Second-Order Recurrence
In a first-order recurrence such as
\[ a_n=2a_{n-1}, \]only one previous value is needed.
In a second-order recurrence such as
\[ a_n=a_{n-1}+a_{n-2}, \]two previous values must be remembered.
The pair
\[ (a_{n-1},a_n) \]contains enough information to generate the next state.
State-Pair Updating
For the Fibonacci recurrence, the state
\[ (a_{n-1},a_n) \]updates to
\[ \boxed{ (a_n,\ a_{n-1}+a_n) }. \]Starting from
\[ (1,1), \]we obtain
\[ (1,2), \] \[ (2,3), \] \[ (3,5), \] \[ (5,8), \]and so on.
Lucas-Type Sequences
Changing the initial values while keeping the Fibonacci recurrence produces related sequences.
For example, the Lucas sequence begins with
\[ L_0=2,\qquad L_1=1 \]and follows
\[ L_n=L_{n-1}+L_{n-2}. \]The sequence is
\[ \boxed{2,\ 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ldots}. \]The recurrence is the same as Fibonacci's; only the initial conditions differ.
Generalized Fibonacci Sequences
Any sequence satisfying
\[ a_n=a_{n-1}+a_{n-2} \]with specified starting values can be viewed as a generalized Fibonacci-type sequence.
For example,
\[ a_1=2,\qquad a_2=3 \]produces
\[ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ldots \]which is a shifted portion of the familiar Fibonacci pattern.
Dependence on Initial Conditions
Compare the sequences generated by
\[ a_n=a_{n-1}+a_{n-2}. \]With
\[ a_1=1,\qquad a_2=1, \]we obtain
\[ 1,\ 1,\ 2,\ 3,\ 5,\ldots \]but with
\[ a_1=1,\qquad a_2=4, \]we obtain
\[ 1,\ 4,\ 5,\ 9,\ 14,\ldots \]The recurrence controls the relationship among terms; the initial values determine which trajectory follows that relationship.
Recurrences Can Produce Negative Terms
Let
\[ a_1=3,\qquad a_2=-1 \]and
\[ a_n=a_{n-1}+a_{n-2}. \]Then
\[ a_3=-1+3=2, \] \[ a_4=2+(-1)=1, \] \[ a_5=1+2=3. \]The sequence begins
\[ \boxed{3,\ -1,\ 2,\ 1,\ 3,\ 4,\ldots}. \]Recurrences Can Produce Oscillation
Consider
\[ a_n=-a_{n-1}+a_{n-2} \]with
\[ a_1=1,\qquad a_2=2. \]Then
\[ a_3=-2+1=-1, \] \[ a_4=-(-1)+2=3, \] \[ a_5=-3+(-1)=-4. \]Recursive rules can therefore create growth, decay, oscillation, or more complicated behavior depending on their coefficients.
From Recurrence to Closed Form
Recursive definitions describe terms through earlier terms.
A closed form or explicit formula attempts to calculate \(a_n\) directly from \(n\).
For the Fibonacci sequence, such a formula exists, but discovering it requires more advanced algebraic ideas.
The recurrence remains the simplest natural definition.
The Characteristic Equation
For a linear recurrence of the form
\[ a_n=pa_{n-1}+qa_{n-2}, \]one useful advanced method begins by trying solutions of the form
\[ a_n=r^n. \]Substitute:
\[ r^n=pr^{n-1}+qr^{n-2}. \]Divide by \(r^{n-2}\) when \(r\neq0\):
\[ r^2=pr+q. \]Rearranging gives the characteristic equation
\[ \boxed{r^2-pr-q=0}. \]The Fibonacci Characteristic Equation
For
\[ F_n=F_{n-1}+F_{n-2}, \]the characteristic equation is
\[ r^2-r-1=0. \]Using the quadratic formula,
\[ r=\frac{1\pm\sqrt5}{2}. \]The two roots are
\[ \phi=\frac{1+\sqrt5}{2} \]and
\[ \psi=\frac{1-\sqrt5}{2}. \]The Golden Ratio
The positive characteristic root
\[ \phi=\frac{1+\sqrt5}{2} \]is called the golden ratio.
Numerically,
\[ \phi\approx1.6180339887. \]It appears naturally in the long-run growth of the Fibonacci sequence.
Ratios of Consecutive Fibonacci Numbers
Consider the ratios
\[ \frac{2}{1}=2, \] \[ \frac{3}{2}=1.5, \] \[ \frac{5}{3}\approx1.667, \] \[ \frac{8}{5}=1.6, \] \[ \frac{13}{8}=1.625. \]As the index grows, these ratios approach
\[ \boxed{\phi=\frac{1+\sqrt5}{2}}. \]This provides an early example of sequence convergence.
Binet's Formula
With the convention
\[ F_0=0,\qquad F_1=1, \]the Fibonacci numbers have the explicit formula
\[ \boxed{ F_n= \frac{\phi^n-\psi^n}{\sqrt5} } \]where
\[ \phi=\frac{1+\sqrt5}{2} \]and
\[ \psi=\frac{1-\sqrt5}{2}. \]This formula is known as Binet's formula.
Why an Integer Sequence Can Involve Irrational Numbers
Binet's formula contains
\[ \sqrt5, \qquad \phi, \qquad \psi, \]even though every Fibonacci number is an integer.
The irrational components combine in such a way that the final result is exactly integral.
This is a useful reminder that intermediate algebraic representations may look very different from the objects they ultimately describe.
Why the Recursive Form Still Matters
Even though Binet's formula is explicit, the recurrence
\[ F_n=F_{n-1}+F_{n-2} \]remains conceptually important because it directly describes how the sequence is generated.
Recursive and explicit descriptions answer different questions:
- the recurrence reveals local structure;
- the closed form reveals direct dependence on \(n\);
- both can describe the same sequence.
Matrix Form of the Fibonacci Recurrence
The Fibonacci recurrence can also be written using matrices.
\[ \begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix}. \]The matrix
\[ \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \]transforms one state pair into the next.
This connects recurrence relations with matrix multiplication, linear algebra, and efficient computation.
Repeated Matrix Iteration
Applying the Fibonacci matrix repeatedly gives
\[ \begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}^{n} \begin{pmatrix} 1\\ 0 \end{pmatrix} \]under the \(F_0=0,\ F_1=1\) convention.
This representation shows that a recurrence can be interpreted as repeated application of a linear transformation.
Fibonacci-Type Counting Problems
Fibonacci recurrences often arise when a counting problem can end in one of two mutually exclusive ways.
If every object of size \(n\) can be formed by extending either:
- an object of size \(n-1\); or
- an object of size \(n-2\),
then the number of objects may satisfy
\[ a_n=a_{n-1}+a_{n-2}. \]Example: Climbing Steps
Suppose a person can climb a staircase by taking either one step or two steps at a time.
Let \(a_n\) be the number of ways to reach step \(n\).
Every route to step \(n\) must arrive from either:
- step \(n-1\) using a one-step move; or
- step \(n-2\) using a two-step move.
Therefore,
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]Initial Conditions in the Staircase Model
One convenient convention is
\[ a_0=1, \]because there is one way to climb zero steps: do nothing.
Also,
\[ a_1=1. \]Then
\[ a_2=2, \] \[ a_3=3, \] \[ a_4=5. \]The count follows a Fibonacci-type pattern.
Recurrences in Population Models
Recurrence relations can model populations when one period depends on several earlier periods.
A simplified model might use
\[ P_n=P_{n-1}+bP_{n-2}, \]where \(b\) represents delayed reproductive contribution.
Real population models are usually more complicated, but the recurrence framework provides a way to represent delayed effects.
Recursive Models with External Input
Some recurrences include an additional term depending on the index:
\[ a_n=a_{n-1}+a_{n-2}+n. \]Here, the next value depends on:
- the two previous states; and
- an external contribution determined by \(n\).
Such rules are called nonhomogeneous recurrences.
Homogeneous and Nonhomogeneous Recurrences
A recurrence such as
\[ a_n=2a_{n-1}+3a_{n-2} \]is homogeneous because every term is built entirely from sequence terms.
A recurrence such as
\[ a_n=2a_{n-1}+3a_{n-2}+5 \]is nonhomogeneous because of the additional constant term \(5\).
This distinction becomes important when solving recurrences systematically.
Order of a Recurrence
The order tells us how far backward the recurrence reaches.
For
\[ a_n=3a_{n-1}, \]the order is \(1\).
For
\[ a_n=a_{n-1}+a_{n-2}, \]the order is \(2\).
For
\[ a_n=a_{n-1}+a_{n-3}, \]the recurrence reaches back three indices, so it is third order.
Higher-Order Fibonacci-Type Recurrences
Fibonacci's rule can be extended to more preceding terms.
For example,
\[ a_n=a_{n-1}+a_{n-2}+a_{n-3} \]adds the previous three terms.
With
\[ a_1=1,\qquad a_2=1,\qquad a_3=2, \]we obtain
\[ a_4=4, \] \[ a_5=7, \] \[ a_6=13. \]The sequence begins
\[ \boxed{1,\ 1,\ 2,\ 4,\ 7,\ 13,\ldots}. \]Higher Order Requires More Initial Data
A third-order recurrence generally requires three initial values.
A fourth-order recurrence generally requires four.
The principle is simple:
\[ \boxed{ \text{the initial conditions must provide enough information to start the recurrence} }. \]Recursive Growth Can Be Fast
Consider
\[ a_n=2a_{n-1}+2a_{n-2} \]with
\[ a_1=1,\qquad a_2=1. \]Then
\[ a_3=4, \] \[ a_4=10, \] \[ a_5=28, \] \[ a_6=76. \]Even simple recurrence rules can generate rapid growth.
Common Error: Using Only One Initial Condition
Suppose a student writes
\[ a_1=2,\qquad a_n=a_{n-1}+a_{n-2}. \]This is incomplete because calculating \(a_3\) requires both \(a_2\) and \(a_1\).
A second initial condition such as
\[ a_2=5 \]is needed.
Common Error: Adding the Wrong Terms
If
\[ a_n=a_{n-1}+a_{n-2}, \]then to find \(a_6\), use
\[ a_6=a_5+a_4. \]Do not use
\[ a_5+a_3 \]or another pair unless the recurrence explicitly says to do so.
Common Error: Updating Too Early
When generating a recurrence computationally, both old values may be needed before either is overwritten.
For the state
\[ (a_{n-1},a_n), \]first compute
\[ a_{n+1}=a_n+a_{n-1}. \]Then shift the state.
Updating one stored value too early can corrupt the next calculation.
Common Error: Assuming Every Recurrence Has a Simple Explicit Formula
Some recurrences have elegant closed forms.
Others do not have elementary explicit formulas that are convenient to use.
A recursive definition can be complete and mathematically useful even when no simple direct formula is available.
Common Error: Confusing a Recurrence with a Pattern Guess
A listed sequence such as
\[ 1,\ 1,\ 2,\ 3,\ 5,\ldots \]suggests the Fibonacci rule.
But the list alone does not logically force that recurrence.
A precise recursive definition states the rule explicitly:
\[ F_n=F_{n-1}+F_{n-2}. \]A Reliable Procedure for Using a Second-Order Recurrence
- Identify the two initial conditions.
- Identify the recurrence relation.
- Check the index at which the recurrence begins.
- Substitute the two required earlier terms.
- Calculate the new term.
- Record the result before moving forward.
- Use the newest two terms to continue the process.
- Repeat until the desired index is reached.
A Reliable Procedure for Analyzing a Fibonacci-Type Rule
- Determine the order of the recurrence.
- Count how many initial conditions are required.
- Identify the coefficients of the earlier terms.
- Check whether any external term depends on \(n\).
- Generate several terms carefully.
- Look for growth, decay, alternation, or repetition.
- Compare ratios or differences if long-run behavior is relevant.
- Consider a characteristic equation for linear homogeneous recurrences.
Example: Full Recurrence Workflow
Let
\[ a_1=2,\qquad a_2=7, \]and
\[ a_n=2a_{n-1}-a_{n-2}. \]Then
\[ a_3=2(7)-2=12, \] \[ a_4=2(12)-7=17, \] \[ a_5=2(17)-12=22. \]Thus,
\[ \boxed{2,\ 7,\ 12,\ 17,\ 22,\ldots}. \]The recurrence unexpectedly generates an arithmetic sequence with common difference \(5\).
Example: A Non-Fibonacci Weighted Recurrence
Let
\[ a_1=1,\qquad a_2=3, \]and
\[ a_n=a_{n-1}+2a_{n-2}. \]Then
\[ a_3=3+2(1)=5, \] \[ a_4=5+2(3)=11, \] \[ a_5=11+2(5)=21, \] \[ a_6=21+2(11)=43. \]Therefore,
\[ \boxed{1,\ 3,\ 5,\ 11,\ 21,\ 43,\ldots}. \]Practice 1: Generate Fibonacci Terms
Given
\[ F_0=0,\qquad F_1=1, \]and
\[ F_n=F_{n-1}+F_{n-2}, \]find
\[ F_2,\ F_3,\ F_4,\ F_5,\ F_6. \]Practice 2: Generalized Fibonacci Sequence
Let
\[ a_1=2,\qquad a_2=6, \]and
\[ a_n=a_{n-1}+a_{n-2}. \]Find the next four terms.
Practice 3: Weighted Recurrence
Let
\[ a_1=1,\qquad a_2=2, \]and
\[ a_n=3a_{n-1}-a_{n-2}. \]Find \(a_3,a_4,a_5\).
Practice 4: Identify the Order
What is the order of
\[ a_n=2a_{n-1}+a_{n-3}? \]Practice 5: Initial Conditions
How many initial values are generally needed for
\[ a_n=a_{n-1}+a_{n-2}+a_{n-3}? \]Practice 6: Characteristic Equation
Write the characteristic equation for
\[ a_n=3a_{n-1}+2a_{n-2}. \]Practice 7: Fibonacci Characteristic Roots
Solve
\[ r^2-r-1=0. \]Practice 8: Staircase Recurrence
A person can climb either one or two steps at a time.
Explain why the number of ways \(a_n\) to reach step \(n\) satisfies
\[ a_n=a_{n-1}+a_{n-2}. \]Practice 9: Matrix State
For the Fibonacci recurrence, write the matrix that transforms
\[ \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} \]into
\[ \begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix}. \]Practice 10: Identify the Error
A student is given
\[ a_n=a_{n-1}+a_{n-2} \]and the single initial value
\[ a_1=5. \]The student says the entire sequence is now determined.
Explain the error.
Practice Answers
Practice 1
\[ F_2=1, \] \[ F_3=2, \] \[ F_4=3, \] \[ F_5=5, \] \[ F_6=8. \]Therefore,
\[ \boxed{0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8}. \]Practice 2
\[ a_3=6+2=8, \] \[ a_4=8+6=14, \] \[ a_5=14+8=22, \] \[ a_6=22+14=36. \]Thus,
\[ \boxed{8,\ 14,\ 22,\ 36}. \]Practice 3
\[ a_3=3(2)-1=5, \] \[ a_4=3(5)-2=13, \] \[ a_5=3(13)-5=34. \]Therefore,
\[ \boxed{a_3=5,\quad a_4=13,\quad a_5=34}. \]Practice 4
The recurrence reaches back to
\[ a_{n-3}. \]Therefore, it is
\[ \boxed{\text{third order}}. \]Practice 5
Because the recurrence depends on the previous three terms, we generally need
\[ \boxed{3\text{ initial values}}. \]Practice 6
Try \(a_n=r^n\):
\[ r^n=3r^{n-1}+2r^{n-2}. \]Divide by \(r^{n-2}\):
\[ r^2=3r+2. \]Therefore,
\[ \boxed{r^2-3r-2=0}. \]Practice 7
By the quadratic formula,
\[ r=\frac{1\pm\sqrt{1+4}}{2} \] \[ =\boxed{\frac{1\pm\sqrt5}{2}}. \]Practice 8
Every path to step \(n\) must end with either:
- a one-step move from step \(n-1\); or
- a two-step move from step \(n-2\).
These two cases are disjoint and exhaust all possibilities, so
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]Practice 9
\[ \boxed{ \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} } \]because
\[ \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix} \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} = \begin{pmatrix} F_n+F_{n-1}\\ F_n \end{pmatrix} = \begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix}. \]Practice 10
A second-order recurrence requires two initial values.
The value \(a_1=5\) alone does not determine \(a_2\), so many different sequences remain possible.
Therefore, a second initial condition such as
\[ a_2=\text{given} \]is required.
What to Remember
The classical Fibonacci recurrence is
\[ \boxed{ F_n=F_{n-1}+F_{n-2} }. \]More generally, a second-order linear recurrence may have the form
\[ \boxed{ a_n=pa_{n-1}+qa_{n-2} }. \]- Second-order recurrences generally require two initial conditions.
- The recurrence controls how terms relate locally.
- The initial conditions determine the particular sequence.
- Different initial values can produce different sequences under the same rule.
- Characteristic equations can help produce explicit formulas.
- The Fibonacci characteristic roots involve the golden ratio.
- Consecutive Fibonacci ratios approach \(\phi\).
- Recurrences connect naturally with algorithms, matrices, counting, and dynamical systems.
The core recursive structure is
\[ \boxed{ \text{stored previous states} \longrightarrow \text{new state} }. \]Where We Go Next
Fibonacci-type recurrences show how a sequence can be generated through dependence on earlier states. The next step is to examine how sequences are represented visually and numerically across indices.
The next lesson, Sequence Tables and Discrete Graphs, develops tabular and coordinate representations of sequences and connects indexed values with discrete functions in the coordinate plane.