Skip to main content

Section 8.5 The Fibonacci Sequence and Higher Order Recursions

In this section, we return to look at higher order recursively-defined sequences, especially the famous Fibonacci sequence. We look at how to model sequences using higher order recursions and how to use recursions to solve counting problems. Next, the Fibonacci sequence has many patterns, which we explore and prove using mathematical induction. Finally, we introduce a strong form of mathematical induction that, among other things, can be used to prove explicit forms for higher order recursively-defined sequences.

Subsection 8.5.A The Fibonacci Sequence and Higher Order Recursions

In the Squares and Dominoes puzzle Activity 2.1.A, the Proper Bit Strings puzzle Activity 8.4.A, and the lopsided tree activity Activity 8.4.C, we saw a sequence where each term was the sum of the two previous terms. The most famous sequence satisfying that recursion is the Fibonacci sequence.

Definition 8.5.1 Fibonacci sequence.

 
  1. The Fibonacci sequence is defined by \(F_0=0\text{,}\) \(F_1=1\) and
    \begin{equation*} F_n=F_{n-1}+F_{n-2} \end{equation*}
    for \(n \ge 2\text{.}\) The sequence begins
    \begin{equation*} 0,1,1,2,3,5,8,13,21,34,55,89, \ldots \end{equation*}
    as we see in Example 8.5.2.
  2. An integer is Fibonacci if it is a term of the Fibonacci sequence. For example, 13 and 89 are Fibonacci.
Let’s see how we found the terms of the Fibonacci sequence.

Example 8.5.2 The Fibonacci sequence.

Find the first twenty terms of the Fibonacci sequence: \(F_0, F_1, \ldots, F_{19}\text{.}\)
Solution.
The initial conditions tell us that \(F_0=0\) and \(F_1=1\text{.}\) Next, we use the recursion with \(n=2\) to get
\begin{equation*} F_2=F_1+F_0 = 1+0=1\text{.} \end{equation*}
Continuing to use the recursion with \(n=\) 3, 4, 5 and 6 we get
\begin{equation*} F_3=F_2+F_1 = 1+1=2\text{,} \end{equation*}
\begin{equation*} F_4=F_3+F_2 = 2+1=3\text{,} \end{equation*}
\begin{equation*} F_5=F_4+F_3 = 3+2=5\text{,} \end{equation*}
and
\begin{equation*} F_6=F_5+F_4 = 5+3=8\text{.} \end{equation*}
We continue this pattern to get the rest of the first twenty terms as listed in Table 8.5.3. For example, when \(n=15\) we have
\begin{equation*} F_{15}=F_{14}+F_{13} = 377+233=610\text{.} \end{equation*}
Table 8.5.3. The first twenty Fibonacci numbers
\(F_0=0\) \(F_5=5\) \(F_{10}=55\) \(F_{15}=610\)
\(F_1=1\) \(F_6=8\) \(F_{11}=89\) \(F_{16}=987\)
\(F_2=1\) \(F_7=13\) \(F_{12}=144\) \(F_{17}=1597\)
\(F_3=2\) \(F_8=21\) \(F_{13}=233\) \(F_{18}=2584\)
\(F_4=3\) \(F_9=34\) \(F_{14}=377\) \(F_{19}=4181\)
Let’s practice using the recursion for the Fibonacci sequence.

Example 8.5.4 Write as a single Fibonacci number.

Use the recursive rule for the Fibonacci sequence to simplify each expression as a single Fibonacci number.
  1. \(F_{98} + F_{99}\)
    Solution.
    The terms \(F_{98}\) and \(F_{99}\) are consecutive terms of the Fibonacci sequence, so their sum equals the next term. In order we have \(F_{98}, F_{99}, F_{100}\text{.}\) Thus, \(F_{98} + F_{99}=F_{100}\text{.}\)
  2. \(F_n+F_{n-1}\)
    Solution.
    The terms \(F_n\) and \(F_{n-1}\) are consecutive terms of the Fibonacci sequence, so their sum equals the next term. In order we have \(F_{n-1}, F_n, F_{n+1}\text{.}\) Thus, \(F_n+F_{n-1}=F_{n+1}\text{.}\)
  3. \(F_{3n} - F_{3n-1}\)
    Solution.
    The terms \(F_{3n}\) and \(F_{3n-1}\) are consecutive terms of the Fibonacci sequence. In order we have \(F_{3n-2}, F_{3n-1}, F_{3n}\text{.}\) Thus, \(F_{3n-2} + F_{3n-1} = F_{3n}\text{.}\) Subtracting \(F_{3n-1}\) from each side of the equation we get \(F_{3n} - F_{3n-1}= F_{3n-2}\text{.}\)
Notice that the recursive rule for the Fibonacci sequence uses two previous terms. We have a name for sequences defined by recursions that use more than one previous term.

Definition 8.5.5 Higher order recursions.

 
  1. A recursive rule that involves the two previous terms is second order. The most famous second order recursion is the Fibonacci sequence.
  2. A recursive rule that involves the \(k\) previous terms is \(k^{\text{ th } }\) order. For example, the tribonacci sequence defined by \(t_0=0\text{,}\) \(t_1=1\text{,}\) \(t_2=1\text{,}\) and \(t_n=t_{n-1}+t_{n-2}+t_{n-3}\) for \(n\ge 3\) is third order.
  3. Note that a recursive of order \(k\) needs \(k\) initial conditions. For example, a first order needs the first term, a second order needs the first two terms, a third order needs the first three terms, and so on.
Let’s look at examples of evaluating higher order recursively-defined sequences.

Example 8.5.6 Evaluating higher order recursively-defined sequences.

Write the first five terms of each sequence. Your list should begin with the initial conditions.
  1. The Lucas sequence is defined by \(L_0=2\text{,}\) \(L_1=1\text{,}\) and
    \begin{equation*} L_n=L_{n-1}+L_{n-2} \end{equation*}
    for \(n\ge 2\text{.}\) The Lucas sequence has the same recursion as the Fibonacci sequence, but because the initial conditions are different we get a different sequence.
    Solution.
    We are told that \(L_0=2\) and \(L_1=1\text{.}\) When \(n=2\text{,}\) the recursion gives us
    \begin{equation*} L_2=L_1+L_0=2+1=3\text{.} \end{equation*}
    Next, when \(n=3\) we get
    \begin{equation*} L_3=L_2+L_1=3+1=4\text{.} \end{equation*}
    Finally, when \(n=4\) we have
    \begin{equation*} L_4=L_3+L_2=4+3=7\text{.} \end{equation*}
    The first five terms of the Lucas sequence are \(2,1,3,5,7\text{.}\)
  2. The sequence \(a_n\) is defined by \(a_1=2\text{,}\) \(a_2=-3\text{,}\) and
    \begin{equation*} a_n=a_{n-2}+(-1)^{n+1}2 \end{equation*}
    for \(n\ge 3\text{.}\) Notice that this sequence is second order, even though \(a_{n-1}\) is not part of the recursion.
    Solution.
    We are told that \(a_1=2\) and \(a_2=-3\text{.}\) When \(n=3\text{,}\) the recursion gives us
    \begin{equation*} a_3=a_1+(-1)^{3+1}2=2+2=4\text{.} \end{equation*}
    Next, when \(n=4\) we get
    \begin{equation*} a_4=a_2+(-1)^{4+1}2=-3-2=-5\text{.} \end{equation*}
    Finally, when \(n=5\) we have
    \begin{equation*} a_5=a_3+(-1)^{5+1}2=4+2=6\text{.} \end{equation*}
    The first five terms are \(2,-3,4,-5,6\text{.}\) We saw this sequence in Example 6.5.8(c) and found an explicit rule for this sequence is \(a_n=(-1)^n(n+2)\) for \(n \ge 0\text{.}\)
  3. The tribonacci sequence \(t_n\) is defined by \(t_0=0\text{,}\) \(t_1=1\text{,}\) \(t_2=1\text{,}\) and
    \begin{equation*} t_n=t_{n-1}+t_{n-2}+t_{n-3} \end{equation*}
    for \(n\ge 3\text{.}\)
    Solution.
    We are told that \(t_0=0\text{,}\) \(t_1=1\text{,}\) and \(t_2=1\text{.}\) When \(n=3\) we get
    \begin{equation*} t_3=t_2+t_1+t_0=1+1+2\text{.} \end{equation*}
    Next, when \(n=4\) we have
    \begin{equation*} t_4=t_3+t_2+t_1=2+1+1=4\text{.} \end{equation*}
    The first five terms of this sequence are \(0,1,1,2,4\text{.}\) We saw this sequence in Section 2.1 Exercise 2 where we were tiling the \(1 \times n\) board using \(1\times 1\) squares, \(1 \times 2\) dominoes, and \(1\times 3\) trominoes.
Try working with the Fibonaccis and higher order recursions.

Activity 8.5.A Higher order recursively-defined sequences.

 
  1. Use the recursion that defines Fibonacci sequence: \(F_n=F_{n-1}+F_{n-2}\) and that \(F_5=5\) and \(F_6=8\) to calculate \(F_7\text{,}\) \(F_8\text{,}\) \(F_9\text{,}\) and \(F_{10}\text{.}\)
  2. Evaluate the first five terms of the sequence defined by \(a_0=3\text{,}\) \(a_1=2\) and
    \begin{equation*} a_n = a_{n-1}+2a_{n-2} \end{equation*}
    for \(n \ge 2\text{.}\) Your list should begin with the initial conditions.
  3. Evaluate \(w_5\) where \(w_0=-1\text{,}\) \(w_1=2\text{,}\) \(w_2=1\) and
    \begin{equation*} w_n = w_{n-1}w_{n-2}w_{n-3} \end{equation*}
    for \(n \ge 3\text{.}\)
  4. Use the recursive rule for the Fibonacci sequence to write \(F_{39} + F_{40}\) as a single Fibonacci number. Repeat for \(F_{n-1} + F_n\text{.}\)

Subsection 8.5.B Modeling with Higher Order Recursions

Higher order recursions can be used to describe sequences and also to count.

Example 8.5.8 Modeling with higher order recursively-defined sequences.

For each list, find a simple pattern generating a sequence. Write the initial conditions and a higher order recursive rule for the sequence. Start your indexing at 0.
  1. The sequence \(a\) begins 2, 5, 6, 10, 15, 24, 38, ….
    Solution.
    Look at what happens when we add consecutive terms. We get \(2+5=7\text{,}\) \(5+6=11\text{,}\) \(6+10=16\text{,}\) and so on. In each case, we get one more than the next term. That is, each term is the one less than the sum of the previous two terms. A recursive definition is \(a_0=2\text{,}\) \(a_1=5\text{,}\) and \(a_n=a_{n-1}+a_{n-2}-1\) for \(n \ge 2\text{.}\)
  2. The sequence \(b\) begins \(2, 5, 10, 50, 500, 25000, \ldots\text{.}\)
    Solution.
    Look at what happens when we multiply consecutive terms. We get \(2 \times 5= 10\text{,}\) \(5 \times 10=50\text{,}\) and \(10 \times 50 = 500\text{.}\) In each case, we get the next term of the sequence. A recursive definition is \(b_0=2\text{,}\) \(b_1=5\text{,}\) and \(b_n=b_{n-1}b_{n-2}\) for \(n \ge 2\text{.}\)
Sometimes there are different order recursions that generate the same sequence.

Example 8.5.9 Different order recursions.

Consider the sequence \(c\) that begins
\begin{equation*} 2, 5, 10, 13, 18, 21, 26, \ldots \end{equation*}
  1. Write a third order recursive definition for the sequence, starting your index at 0.
    Solution.
    We want to combine 2, 5, and 10 to make 13 and then use the same combination with 5, 10, and 13 to make 18. Note that \(13 = 10 + 5-2\) and \(18 = 13 + 10 -5\text{.}\) A recursion is \(c_0=2\text{,}\) \(c_1=5\text{,}\) \(c_2=10\text{,}\) and \(c_n=c_{n-1}+c_{n-2}-c_{n-3}\) for \(n \ge 3\text{.}\)
  2. Write a first order recursive definition for the sequence, starting your index at 0.
    Solution.
    Notice how we can add either three or five to get from each term to the next:
    \begin{equation*} 2 \xrightarrow[+ 3]{} 5 \xrightarrow[+ 5]{} 10 \xrightarrow[+ 3]{} 13 \xrightarrow[+ 5]{} 18 \xrightarrow[+ 3]{} 21 \xrightarrow[+ 5]{} 26\text{.} \end{equation*}
    Since the number we add alternates, the formula involves \((-1)^n\text{.}\) Using that \(3 = 4-1\) and \(5 = 4+1\) we get the first order recursive definition \(c_0=2\) and \(c_n=c_{n-1}+4+(-1)^n\) for \(n \ge 1\text{.}\)
Recursions can also be used to list or count objects. Let’s start with a first order recursion to get the idea.

Example 8.5.10 Using a recursion to count bit strings containing at least one \(\bs{0}\).

  How many bit strings of length \(n\) include at least one \(\bs{0}\text{?}\) Count directly and then show how to write a recursion to count.
Solution.
By Theorem 2.4.8, there are \(2^n\) bit strings of length \(n\text{.}\) The only bit string that does not have any \(\bs{0}\) s is \(\bs{11}\) \(\cdots\) \(\bs{1}\text{.}\) Therefore, by Theorem 2.2.9, there are \(2^n-1\) bit strings of length \(n\) that include at least one \(\bs{0}\text{.}\)
How can we write a recursion to count? Write \(z_n=\) the number of bit strings of length \(n\) that include at least one \(\bs{0}\text{.}\) Note that the only bit string of length 1 that includes at least one \(\bs{0}\) is \(\bs{0}\) itself and so \(z_1=1\text{.}\) Given a bit string of length \(n\) that has at least one \(\bs{0}\text{,}\) we consider two cases.
Case 1: The bit string begins with \(\bs{1}\text{.}\) In this case, the other \(n-1\) bits must include at least one \(\bs{0}\text{.}\) There are \(z_{n-1}\) such bit strings.
Case 2: The bit string begins with \(\bs{0}\text{.}\) In this case, we have at least one \(\bs{0}\) no matter what the other \(n-1\) bits are. They can be any bit string of length \(n-1\text{.}\) By Theorem 2.4.8, there are \(2^{n-1}\) bit strings of length \(n-1\text{.}\) Therefore, there are \(2^{n-1}\) such bit strings.
Since cases add Theorem 2.2.7, we get
\begin{equation*} z_n=z_{n-1}+2^{n-1} \end{equation*}
for \(n\ge 2\) and the initial condition is \(z_1=1\text{.}\)
We can also count using higher order recursions.

Example 8.5.11 Using a recursion to count bit strings that do not contain \(\bs{00}\).

Write a recursion that counts the number of bit strings of length \(n\) that do not contain \(\bs{00}\text{,}\) meaning they do not contain two or more consecutive zeros.
Solution.
Write \(c_n=\) the number of bit strings of length \(n\) that do not contain \(\bs{00}\text{.}\) Note that neither bit strings of length 1 contains \(\bs{00}\) and so \(c_1=2\text{.}\) Also note that three of the bit strings of length 2 do not contain \(\bs{00}\text{,}\) namely \(\bs{01}\text{,}\) \(\bs{10}\text{,}\) and \(\bs{11}\text{,}\) and so \(c_2=3\text{.}\) Given a bit string of length \(n\) that does not include \(\bs{00}\text{,}\) we consider two cases.
Case 1: The bit string begins with \(\bs{1}\text{.}\) In this case, the other \(n-1\) bits cannot include \(\bs{00}\text{.}\) There are \(c_{n-1}\) such bit strings.
Case 2: The bit string begins with \(\bs{0}\text{.}\) In this case, the next bit must be \(\bs{1}\) so that we avoid \(\bs{00}\text{.}\) The other \(n-2\) bits cannot include \(\bs{00}\text{.}\) There are \(c_{n-2}\) such bit strings.
Since cases add Theorem 2.2.7, we have
\begin{equation*} c_n=c_{n-1}+c_{n-2} \end{equation*}
for \(n\ge 3\) and initial conditions \(c_1=2\) and \(c_2=3\text{.}\)
Try modeling with higher order recursively-defined sequences.

Activity 8.5.B Modeling with higher order recursively-defined sequences.

 
  1. Find a simple pattern generating a sequence \(a\) that begins
    \begin{equation*} 3, 1, 5, 7, 13, 21, 35, 57, \ldots \end{equation*}
    Write the initial conditions and a higher order recursive rule for the sequence. Start your indexing at 0. Hint: Start by adding the two previous terms.
  2. We want to tile a \(1 \times n\) board using \(1 \times 1\) squares that are either red (\(\str{R}\)), blue (\(\str{B}\)), and green (\(\str{G}\)) in such a way that we never place two red tiles next to each other. That is, the tiling does not contain \(\str{RR}\text{.}\) Let \(t_n=\) the number of such tilings. Write a second order recursive definition for \(t_n\text{,}\) including two initial conditions. Hint: Break into cases based on whether the tiling starts with \(\str{G}\text{,}\) \(\str{B}\text{,}\) or \(\str{R}\text{.}\) In the case where it starts with \(\str{R}\text{,}\) explaining why the next tile must be \(\str{B}\) or \(\str{G}\text{.}\)

Subsection 8.5.C Detour: Fibonacci Patterns and Proof

There are many patterns satisfied by the Fibonacci sequence.

Activity 8.5.C Fibonacci patterns.

For this activity, it is useful have a list of the first twenty Fibonacci numbers, as in Table 8.5.3.
  1. Which Fibonacci numbers are even? Begin your conjecture “\(F_n\) is even if …”.
  2. Something interesting happens when you multiply a Fibonacci number and the Fibonacci number two later in the sequence. For example,
    \begin{equation*} F_4 \cdot F_6 = (3)(8) = 24 = 5^2 -1 = F_5^2 - 1 \end{equation*}
    and
    \begin{equation*} F_5 \cdot F_7 = (5)(13) = 65 = 8^2 + 1 = F_6^2 + 1\text{.} \end{equation*}
    What’s the general pattern? State your answer as a conjecture.
  3. Use the Euclidean Algorithm Subsection 4.5.B to evaluate \(\fn{gcd}(F_8,F_7)=\fn{gcd}(21,13)\text{.}\) What do you notice? Hint: Recall that the first two steps are \(21 \fn{ mod } 13 = 8\) and then \(13 \fn{ mod } 8 = 5\text{.}\)
  4. Consider the \(2 \times 2\) matrix \(A= \left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\text{.}\) Calculate \(A^2\text{,}\) \(A^3\text{,}\) and \(A^4\) as defined in Definition 8.3.1 and conjecture the explicit formula for \(A^n\text{.}\)
Let’s explore some patterns similar to Activity 8.5.C and also discuss how to prove these patterns hold. First, we look at a divisibility statement that involves the Fibonacci sequence.

Example 8.5.14 Fibonacci numbers that are multiples of three.

 
  1. When does \(3 \mid F_n\text{?}\) State your answer as a conjecture.
    Solution.
    The first few Fibonacci numbers that are divisible by 3 are \(F_4=3\text{,}\) \(F_8=21\text{,}\) \(F_{12}=144\text{,}\) and \(F_{16}=987\text{.}\) It appears that \(3 \mid F_n\) when \(4 \mid n\text{.}\) Notice that \(3=F_4\) so we can get fancy and rewrite our conjecture as \(F_4 \mid F_n\) when \(4 \mid n\text{.}\) We can also write our conjecture explicitly as \(3 \mid F_{4n}\text{.}\)
  2. Use the recursive rule and algebra to prove \(F_{4n} =5F_{4n-4} + 3F_{4n-5}\) for \(n \ge 0\text{.}\)
    Solution.
    The recursive rule for the Fibonacci sequence allows us to write any Fibonacci number as the sum of the two preceding Fibonacci numbers. We repeatedly use this idea, and simplify by collecting like terms, to get
    \begin{align*} F_{4n} \amp = F_{4n-1} + F_{4n-2}\\ \amp = \left(F_{4n-2}+F_{4n-3}\right) + F_{4n-2}\\ \amp = 2F_{4n-2} + F_{4n-3}\\ \amp = 2 \left(F_{4n-3}+F_{4n-4}\right) + F_{4n-3}\\ \amp = 3 F_{4n-3}+2F_{4n-4}\\ \amp = 3 \left(F_{4n-4} + F_{4n-5}\right) +2F_{4n-4}\\ \amp = 5 F_{4n-4} + 3F_{4n-5}\text{.} \end{align*}
    Whew!
  3. Use the identity from (b) and mathematical induction to prove that \(3 \mid F_{4n}\) for \(n \ge 0\text{.}\)
    Solution.
    Proof First, when \(n=0\) we have \(F_{4(0)}=F_0=0\) and \(3 \mid 0\) so \(3 \mid F_{4(0)}\text{.}\)
    Next, assume \(3 \mid F_{4(n-1)} = F_{4n-4}\) for some integer \(n > 0\text{.}\) By the definition of divides we can write \(F_{4n-4}=3k\) for some integer \(k\text{.}\) Then using the identity from (b) we have
    \begin{align*} F_{4n} \amp = 5 F_{4n-4} + 3F_{4n-5}\\ \amp = 5(3k) + 3F_{4n-5}\\ \amp = 3(5k+F_{4n-5})\text{.} \end{align*}
    Thus \(3 \mid F_{4n}\text{.}\)
Let’s look at the greatest common divisor of Fibonacci numbers.

Example 8.5.15 Fibonaccis and the \(\fn{gcd}\).

 
  1. Use the Euclidean Algorithm Subsection 4.5.B to evaluate \(\fn{gcd}(F_{10},F_9)=\fn{gcd}(55,34)\text{.}\) What do you notice?
    Solution.
    The steps of the Euclidean Algorithm are
    \begin{equation*} 55 \fn{ mod } 34 = 21 \end{equation*}
    \begin{equation*} 34 \fn{ mod } 21 = 13 \end{equation*}
    \begin{equation*} 21 \fn{ mod } 13 = 8 \end{equation*}
    \begin{equation*} 13 \fn{ mod } 8 = 5 \end{equation*}
    \begin{equation*} 8 \fn{ mod } 5 = 3 \end{equation*}
    \begin{equation*} 5 \fn{ mod } 3 = 2 \end{equation*}
    \begin{equation*} 3 \fn{ mod } 2 = 1 \end{equation*}
    \begin{equation*} 2 \fn{ mod } 1 = 0 \end{equation*}
    Thus, \(\fn{gcd}(55,34)=1\text{.}\) They are coprime.
    Notice how we calculated each of the previous Fibonacci numbers. In fact, the Fibonacci are a “worst-case scenario” for the Euclidean Algorithm, meaning it takes the most steps possible relatively to the size of the integers.
  2. Use the Euclidean Algorithm Subsection 4.5.B to evaluate \(\fn{gcd}(F_{12},F_9)=\fn{gcd}(144,34)\text{.}\) What do you notice?
    Solution.
    The steps of the Euclidean Algorithm are
    \begin{equation*} 144 \fn{ mod } 34 = 8 \end{equation*}
    \begin{equation*} 34 \fn{ mod } 8 = 2 \end{equation*}
    \begin{equation*} 8 \fn{ mod } 2 = 0\text{.} \end{equation*}
    Thus \(\fn{gcd}{144,34} = 2\text{.}\)
    Look what happens if we write the answer in terms of the Fibonacci numbers. We get \(\fn{gcd}(F_{12},F_9)=F_3\text{.}\)
Next, let’s look at the matrix with powers that involve the Fibonacci sequence from Activity 8.5.C.

Example 8.5.16 Fibonacci matrix.

Consider the \(2 \times 2\) matrix \(A= \left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\text{.}\)
  1. Calculate \(A^2\text{,}\) \(A^3\text{,}\) and \(A^4\text{.}\)
    Solution.
    First,
    \begin{equation*} A^2= \left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]= \left[ \begin{array}{cc} 2 \amp 1\\ 1 \amp 1 \end{array} \right] \end{equation*}
    Next,
    \begin{equation*} A^3= A\cdot A^2=\left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\left[ \begin{array}{cc} 2 \amp 1\\ 1 \amp 1 \end{array} \right]= \left[ \begin{array}{cc} 3 \amp 2\\ 2 \amp 1 \end{array} \right] \end{equation*}
    Last,
    \begin{equation*} A^4= A\cdot A^3=\left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\left[ \begin{array}{cc} 3 \amp 2\\ 2 \amp 1 \end{array} \right]= \left[ \begin{array}{cc} 5 \amp 3\\ 3 \amp 2 \end{array} \right] \end{equation*}
  2. Make a conjecture about an explicit formula for \(A^n\text{.}\)
    Solution.
    Notice that each power of \(A\) has Fibonacci numbers as entries. For example,
    \begin{equation*} A^4= \left[ \begin{array}{cc} 5 \amp 3\\ 3 \amp 2 \end{array} \right] = \left[ \begin{array}{cc} F_5 \amp F_4\\ F_4 \amp F_3 \end{array} \right]\text{.} \end{equation*}
    We might reasonably conjecture that
    \begin{equation*} A^n= \left[ \begin{array}{cc} F_{n+1} \amp F_n \\ F_n \amp F_{n-1} \end{array} \right] \end{equation*}
    for \(n \ge 1\text{.}\)
  3. Use mathematical induction Theorem 8.3.6 to prove your conjecture.
    Solution.
    Proof. Induct on \(n\text{.}\) Write \(M_n = \left[ \begin{array}{cc} F_{n+1} \amp F_n \\ F_n \amp F_{n-1} \end{array} \right]\text{.}\)
    First, when \(n=1\) we have \(A^1=A = \left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\) and \(M_1 = \left[ \begin{array}{cc} F_{2} \amp F_1 \\ F_1 \amp F_0 \end{array} \right] = \left[ \begin{array}{cc} 1 \amp 1 \\ 1 \amp 0 \end{array} \right]\text{.}\)
    Next, assume
    \begin{equation*} A^{n-1} = M_{n-1} = \left[ \begin{array}{cc} F_n \amp F_{n-1} \\ F_{n-1} \amp F_{n-2} \end{array} \right] \end{equation*}
    for some integer \(n > 1\text{.}\) Then
    \begin{align*} A^n \amp = AA^{n-1}\\ \amp = \left[ \begin{array}{cc} 1 \amp 1\\ 1 \amp 0 \end{array} \right]\left[ \begin{array}{cc} F_n \amp F_{n-1}\\ F_{n-1} \amp F_{n-2} \end{array} \right]\\ \amp = \left[ \begin{array}{cc} F_n+F_{n-1} \amp F_{n-1}+F_{n-2}\\ F_n \amp F_{n-1} \end{array} \right]\\ \amp = \left[ \begin{array}{cc} F_{n+1} \amp F_n\\ F_n \amp F_{n-1} \end{array} \right]\\ \amp =M_n\text{.} \end{align*}

Subsection 8.5.D Proof Format: Strong Mathematical Induction

There are stronger forms of mathematical induction for proving some statement \(P(n)\) for all integers \(n \ge s\) for some integer \(s\text{.}\) In this section we look at two special cases.
First, we consider the case where \(P(n)\) can be defined using a single initial condition and some recursion. In this case, the proof begins with the same base case, where we check \(P(s)\text{.}\) In the induction step, instead of just assuming \(P(n-1)\text{,}\) we assume \(P(k)\) for \(k= s, s+1, \ldots, n-2, n-1\text{.}\) That is, we assume \(P(k)\) whenever \(s \le k \lt n\text{.}\) As before, we use this assumption to prove \(P(n)\text{.}\) Here is the formal proof format.
We consider an example.

Example 8.5.18 Using strong mathematical induction.

Use (first-order) strong mathematical induction Theorem 8.5.17 to prove that every integer can be written as the product of a power of two and an odd integer.
Solution.
Proof Induct on \(n\text{.}\)
First, when \(n=1\) we can write \(1=2^0(1)\) which is a product of a power of two (namely \(2^0\)) and an odd integer (namely 1) so the result holds.
Next, assume for some integer \(n > 1\) that any integer \(k\) with \(1 \le k\lt n\) can be written as the product of a power of two and an odd integer. We consider two cases.
Case 1: \(n\) is odd. In this case, \(n = 2^0(n)\) which is the product of a power of two (namely \(2^0\)) and an odd integer (namely \(n\)) so the result holds.
Case 2: \(n\) is even. In this case, by definition of even we can write \(n = 2k\) for some integer \(k\text{.}\) Note that \(1 \le k\lt n\) so by our inductive hypothesis, \(k\) can be written as the product of a power of two and an odd integer. Write \(k = 2^im\) where \(i\) is a nonnegative integer and \(m\) is an odd integer. Then
\begin{equation*} n=2k=2\left(2^im\right)=2^{i+1}m \end{equation*}
which is the product of a power of two (namely \(2^{i+1}\)) and an odd integer (namely \(m\)).
In either case, \(n\) can be written as the product of a power of two and an odd integer.
There is another special case of strong mathematical induction we can use to verify an explicit rule for a second-order recursively-defined sequence. Strong mathematical induction can be extended to any higher order recursion.
As usual, when we introduce a new proof format, we give you an example of a proof to copy and edit.

Activity 8.5.D Strong mathematical induction.

In Example 8.5.6 we saw the Lucas numbers defined by \(L_0=2\text{,}\) \(L_1=1\text{,}\) and
\begin{equation*} L_n=L_{n-1}+L_{n-2} \end{equation*}
for \(n \ge 2\text{.}\) As usual, the Fibonacci sequence is defined by \(F_0=0\text{,}\) \(F_1=1\text{,}\) and
\begin{equation*} F_n=f_{n-1}+F_{n-2} \end{equation*}
for \(n \ge 2\text{.}\)
  1. Copy the following proof. Use mathematical induction Theorem 8.5.19 to prove that
    \begin{equation*} L_n = 2F_{n+1}-F_{n} \end{equation*}
    for all integers \(n \ge 0\text{.}\)

    Proof.
    Write \(f(n) = 2F_{n+1}-F_{n}\text{.}\) Induct on \(n\text{.}\)
    First, when \(n=0\) we have \(L_0=2\) and also
    \begin{equation*} f(0) =2F_1-F_0=2(1)-(0)=2 \text{.} \end{equation*}
    Similarly, when \(n=1\) we have \(L_1=1\) and also
    \begin{equation*} f(1) =2F_2-F_1=2(1)-(1)=1 \text{.} \end{equation*}
    Next, assume
    \begin{equation*} L_{n-1} = f(n-1)= 2F_n-F_{n-1} \end{equation*}
    and
    \begin{equation*} L_{n-2} = f(n-2) = 2F_{n-1}-F_{n-2} \end{equation*}
    for some integer \(n>1\text{.}\)
    Then
    \begin{align*} L_n \amp = L_{n-1}+L_{n-2}\\ \amp = \left(2F_{n}-F_{n-1}\right) + \left(2F_{n-1}-F_{n-2}\right)\\ \amp = 2F_{n}+2F_{n-1} -F_{n-1}-F_{n-2}\\ \amp = 2\left(F_{n}+F_{n-1}\right)-\left(F_{n-1}+F_{n-2}\right)\\ \amp = 2F_{n+1}-F_n\\ \amp = f(n) \end{align*}
  2. Explain the algebra step-by-step in the last chain of equations of the proof.
  3. The sequence \(v\) is defined by \(v_1=1\text{,}\) \(v_2=1\text{,}\) and
    \begin{equation*} v_n=v_{n-1}+v_{n-2}+1 \end{equation*}
    for \(n \ge 3\text{.}\) The sequence \(w\) is defined by \(w_3=2\text{,}\) \(w_4=3\text{,}\) and
    \begin{equation*} w_n = w_{n-1}+w_{n-2} \end{equation*}
    for \(n\ge 5\text{.}\) Use mathematical induction Theorem 8.5.19 to prove that
    \begin{equation*} v_n=2w_n-1 \end{equation*}
    for \(n \ge 3\text{.}\) Note: We saw these two sequences in Activity 8.4.C where we recursively defined the lopsided trees \(T_n\text{.}\) In that activity \(w_n=\) the number of leaves in \(T_n\) and \(v_n=\) the number of vertices in \(T_n\text{.}\)
Let’s look at another example of using strong mathematical induction to verify the explicit form of a second order recursively-defined sequence.

Example 8.5.21 Verifying the explicit form of second order recursively-defined sequence.

Consider the sequence \(a_n\) defined recursively by \(a_0= 1\text{,}\) \(a_1 =6\text{,}\) and
\begin{equation*} a_n =6a_{n-1} -9a_{n-2} \end{equation*}
for \(n \ge 2\text{.}\) Use mathematical induction Theorem 8.5.19 to prove that \(a_n = (n+1)3^n\) for \(n \ge 0\text{.}\)
Solution.
Proof. Write \(f(n) = (n+1)3^n\text{.}\) Induct on \(n\text{.}\)
First, when \(n=0\) we have \(a_0=1\) and
\begin{equation*} f(0)=(1)3^0=1\cdot 1 = 1\text{.} \end{equation*}
Similarly, when \(n=1\) we have \(a_1=6\) and
\begin{equation*} f(1)=(2)3^1= 2\cdot 3 = 6\text{.} \end{equation*}
Next, assume
\begin{equation*} a_{n-1}=f(n-1)=n\cdot 3^{n-1} \end{equation*}
and
\begin{equation*} a_{n-2}=f(n-2)=(n-1)\cdot 3^{n-2} \end{equation*}
for some integer \(n > 1\text{.}\) Then
\begin{align*} a_n \amp = 6a_{n-1} -9a_{n-2}\\ \amp = 6f(n-1)-9f(n-2)\\ \amp = 6\left(n3^{n-1}\right) -9\left((n-1)3^{n-2}\right)\\ \amp = n\cdot 6\cdot 3^{n-1}- (n-1)\cdot 9 \cdot 3^{n-2}\\ \amp = n\cdot 2 \cdot 3 \cdot 3^{n-1}- (n-1)\cdot 3^2 \cdot 3^{n-2}\\ \amp = n\cdot 2 \cdot 3^n- (n-1) \cdot 3^n\\ \amp =(2n-(n-1))3^n\\ \amp = (n+1)3^n \end{align*}
Notice it was convenient to write \(6=2\cdot 3\) because \(3 \cdot 3^{n-1} = 3^n\text{.}\) Similarly, it was convenient to write \(9 = 3^2\) because \(3^2\cdot3^{n-2}=3^n\text{.}\)

Subsection 8.5.E Exercises

Subsubsection Exercises for 8.5.A The Fibonacci Sequence and Higher Order Recursions

2. Practice.

Evaluate the first five terms of each sequence. Your list should begin with the initial conditions.
  1. The sequence defined by \(a_1=3\text{,}\) \(a_2=2\) and \(a_i = a_{i-1}a_{i-2}\) for \(i \ge 3\text{.}\)
  2. The sequence defined by \(b_0=3\text{,}\) \(b_1=2\) and \(b_k=2b_{k-1}-b_{k-2}\) for \(k\ge 2\text{.}\)
  3. The sequence defined by \(c_1=2\text{,}\) \(c_2=1\text{,}\) \(c_3=0\) and \(c_n = c_{n-1} + 2c_{n-3}\) for \(n \ge 4\text{.}\)
Check.
  1. Hint: \(a_5=72\)
  2. Hint: \(b_4=-1\)
  3. Hint: \(c_5=6\)

3. Understand.

Use the recursive rule for the Fibonacci sequence to simplify each expression as a single Fibonacci number.
  1. \(\displaystyle F_{23}+F_{24}\)
  2. \(\displaystyle F_{n-1}+F_{n-2}\)
  3. \(\displaystyle F_{n+1}+F_n\)
  4. \(\displaystyle F_{2n-1}+F_{2n-2}\)
  5. \(\displaystyle F_{2n}-F_{2n-1}\)

4. Understand.

 
  1. Evaluate \(u_4\) where \(u_0=2\text{,}\) \(u_1=2\) and \(u_n = u_{n-1}u_{n-2}\) for \(n \ge 2\text{.}\)
  2. Evaluate \(v_4\) where \(v_1=2\text{,}\) \(v_2=3\) and \(v_m = v_{m-1}(v_{m-2}+1)\) for \(m \ge 3\text{.}\)
  3. Evaluate \(x_6\) where \(x_1=2\text{,}\) \(x_2=1\text{,}\) \(x_3=3\) and \(x_j = 2x_{j-1} - x_{j-3}\) for \(j \ge 4\text{.}\)
Check.
The answers, in some order, are 18, 32, and 36.

5. Understand.

 
  1. Evaluate the first five terms of the sequence defined by \(c_0=1\text{,}\) \(c_1=2\text{,}\) \(c_2=3\) and \(c_n = c_{n-1}+c_{n-2}-c_{n-3}\) and \(n \ge 3\text{.}\) Your list should begin with the initial conditions.
  2. Conjecture an explicit rule for the sequence.

6. Recap.

Do you know …
  1. What the initial conditions and recursive rule are that define the Fibonacci sequence?
  2. How to list the first ten terms of the Fibonacci sequence?
  3. What the order of a recursion is?
  4. How to list the first several terms of a higher order recursively-defined sequence?
  5. Why we need more than one initial condition in the definition of a higher order recursion?

Subsubsection Exercises for 8.5.B Modeling with Higher Order Recursions

7. Practice.

For each list, find a simple pattern generating a sequence. Write the initial conditions and a second order recursive rule for the sequence. Start your indexing at 0 or 1 (your choice).
  1. \(3, 1, 4, 5, 9, 14, 23, 37, \underline{\hspace{.3in}~}, \ldots\text{.}\)
  2. \(\displaystyle 2, 5, -3, 8, -11, 19, -30, 49, \underline{\hspace{.3in}~}, \ldots\)
  3. \(\displaystyle 3, 10, 30, 300, 9000, 2700000 \underline{\hspace{.3in}~}, \ldots\)
Check.
  1. Hint: Add
  2. Hint: Subtract
  3. Hint: Multiply

8. Understand.

Let \(b_n\) count the number of ways to tile a \(1 \times n\) grid using squares (\(1 \times 1\)) and triominoes (\(1 \times 3\)).
  1. Calculate \(b_1\text{,}\) \(b_2\text{,}\) \(b_3\text{,}\) and \(b_4\) by listing the options.
  2. Find a higher order recursive definition for \(b_n\text{,}\) including initial conditions and explain your reasoning.
  3. Check that your recursion gives the correct value for \(b_4\text{.}\)

9. Understand.

We want to count ways to tile a \(1 \times n\) board using red (\(\str{R}\)), blue (\(\str{B}\)), and green (\(\str{G}\)) \(1 \times 1\) square tiles.
  1. Let \(a_n\) be the number of tilings that do not use any blue tiles. Write an explicit rule for \(a_n\text{.}\)
  2. Let \(b_n\) be the number of tilings that contain at least one blue tile. First, write an explicit rule for \(b_n\) and then, write a recursive definition for \(b_n\text{.}\) Hint: Break into cases based on whether the tiling starts with \(\str{G}\text{,}\) \(\str{B}\text{,}\) or \(\str{R}\text{.}\)
  3. Let \(c_n\) be the number of tilings where any green tile is immediately followed by a blue tile. Write a recursive definition for \(c_n\text{.}\)
Check.
  1. Hint: There are two choices for each tile. Steps multiply.
  2. Hint: For the explicit formula use your answer to 9.(a). For the recursive formula, if it starts with \(\str{R}\) or \(\str{G}\text{,}\) then the remainder must include \(\str{B}\text{,}\) but if it starts with \(\str{B}\text{,}\) then the remainder can be any tiling using the three colors.
  3. Hint: Break into cases based on whether the tiling starts with \(\str{G}\text{,}\) \(\str{B}\text{,}\) or \(\str{R}\text{.}\)

10. Understand.

Calculate the initial conditions and write a recursive rule defining \(r_n=\) the number of bit strings of length \(n\) that do not contain \(\bs{000}\text{,}\) meaning that do not contain three or more consecutive \(\bs{0}\) s, for \(n \ge 1\text{.}\) Hint: Look at Example 8.5.11. What are the cases here?

11. Recap.

Do you know …
  1. How to find a higher order recursive definition for a sequence?
  2. Why we might use recursions to count?
  3. How to count using recursions?
  4. How many initial conditions we need to define a higher order recursively-defined sequence?

12. Explore.

Watch a video that explains how to count partitions of an integer (as defined in Section 7.3) using recursions.
  1. According to the video, what is \(P_k(n)\text{?}\)
  2. Copy the final recursion they present for calculating \(P_k(n)\text{.}\)
  3. What were the two cases they used to get this recursion?

Subsubsection Exercises for 8.5.C Detour: Fibonacci Patterns and Proof

13. Practice.

 
  1. Which Fibonacci numbers are divisible by 5? Include some examples to support your conjecture.
  2. Which Fibonacci numbers are divisible by 8? Include some examples to support your conjecture.
Check.
  1. Hint: 0, 5, 55, and 610 are all divisible by 5. Which terms of the Fibonacci sequence are those?
  2. Hint: \(8 \mid 2584\)

14. Practice.

Consider the \(2 \times 2\) matrix \(B= \left[\begin{array}{cc} 0 \amp 1\\ 1 \amp 1 \end{array} \right]\text{.}\)
  1. Calculate \(B^2\text{,}\) \(B^3\text{,}\) and \(B^4\text{.}\)
  2. Make a conjecture about an explicit formula for \(B^n\text{.}\)
Check.
  1. Hint: \(B^4=\left[\begin{array}{cc} 2 \amp 3\\ 3 \amp 5 \end{array} \right]\text{.}\)
  2. Hint: It involves \(F_{n-1}\text{,}\) \(F_n\text{,}\) and \(F_{n+1}\text{.}\)

15. Practice.

In each part, find the \(\str{gcd}\) using the Euclidean Algorithm.
  1. Evaluate \(\fn{gcd}(F_4,F_6)\text{.}\)
  2. Evaluate \(\fn{gcd}(F_6,F_9)\text{.}\)
  3. Evaluate \(\fn{gcd}(F_5,F_{11})\text{.}\)
  4. Evaluate \(\fn{gcd}(F_{10},F_{15})\text{.}\)
Check.
The answers, in some order, are 1 (twice), 2, and 5.

16. Understand.

 
  1. Evaluate \(F_2F_4+F_3F_5\) and write your answer as a single Fibonacci number.
  2. Evaluate \(F_4F_7+F_5F_8\) and write your answer as a single Fibonacci number.
  3. Conjecture how to write \(F_kF_n+F_{k+1}F_{n+1}\) as a single Fibonacci number.

17. Understand.

Prove that the Fibonacci numbers satisfy the identity
\begin{equation*} F_{3n}= 2F_{3n-2}+F_{3n-3} \end{equation*}
for \(n \ge 1\text{.}\)
Check.
Hint: First, use the recursive definition for the Fibonacci sequence to write \(F_{3n}=F_{3n-1} + F_{3n-2}\text{.}\) Next, use the definition again to write \(F_{3n-1}=F_{3n-2}+F_{3n-3}\text{.}\) Finally, put these equations together and simplify by collecting like terms.

18. Understand.

Copy and edit the proof from Example 8.5.14 (c) to use mathematical induction to prove that \(F_{3n}\) is even for \(n \ge 0\text{.}\)
Check.
Hint: The inductive hypothesis is that \(F_{3(n-1)}=F_{3n-3}\) is even. Use the identity from Exercise 17.

19. Understand.

Use the recursive rule and algebra to prove \(F_{5n} =5F_{5n-4} + 3F_{5n-5}\) for \(n \ge 0\text{.}\)

20. Understand.

Use mathematical induction and the identity from Exercise 19 to prove that \(5 \mid F_{5n}\) for \(n \ge 0\text{.}\)

21. Understand.

Consider the \(2 \times 2\) matrix \(B= \left[ \begin{array}{cc} 0 \amp 1\\ 1 \amp 1 \end{array} \right]\text{.}\) Use mathematical induction Theorem 8.3.6 to prove your conjecture about \(B^n\) from Exercise 14.
Check.
Hint: Copy and edit the proof from Example 8.5.16 (c).

22. Understand greatest common divisors of Fibonaccis conjecture.

 
  1. In Example 8.5.15, we saw \(\fn{gcd}(F_{10},F_{9}) = 1 = F_1\) and \(\fn{gcd}(F_{12},F_9)=F_3\text{.}\) Now write each of your answers to Exercise 15 as a Fibonacci number.
  2. Conjecture how to write \(\fn{gcd}(F_m,F_n)\) as a Fibonacci number.

23. Recap.

Do you know …
  1. How to recognize and describe patterns in the Fibonacci sequence?
  2. How to prove Fibonacci identities using the recursion and algebra?
  3. How to prove divisibility statements about the Fibonaccis using mathematical induction?
  4. SU: Anything else here??

25. Explore.

Use mathematical induction to prove that consecutive Fibonacci numbers are coprime, meaning \(\fn{gcd}(F_n,F_{n+1})=1\text{.}\) Hint: In the inductive step, write \(d = \fn{gcd}(F_n,F_{n+1})\) and note \(d \ge 1\text{.}\) By definition of greatest common divisor, it follows that \(d \mid F_n\) and \(d \mid F_{n+1}\text{.}\) Use the recursive rule for the Fibonacci sequence to show that \(d \mid F_{n-1}\text{.}\) Since then \(d \mid F_{n-1}\) and \(d \mid F_n\text{,}\) it follows that \(d\) is a positive common divisor of \(F_{n-1}\) and \(F_n\text{.}\) Explain why it follows that \(d=1\text{.}\)

26. Explore.

Use mathematical induction to prove our conjecture from Activity 8.5.C (b) that
\begin{equation*} F_{n-1} F_{n+1} = F_n^2 + (-1)^n \end{equation*}
for \(n \ge 1\text{.}\) Hint: During the inductive step write \(F_{n-1} F_{n+1} = F_{n-1}\left(F_n+F_{n-1}\right)\text{.}\) Then replace \((F_{n-1})^2\) using the inductive hypothesis. Note that \(-(-1)^{n-1}= (-1)(-1)^{n-1}=(-1)^n\text{.}\)

Subsubsection Exercises for 8.5.D Proof Format: Strong Mathematical Induction

27. Practice.

For Activity 8.4.A, we defined proper bit strings. Use strong mathematical induction Theorem 8.5.17 to prove that any proper bit string has an even number of \(\bs{1}\) s. Hint: In the inductive step consider two cases based on if the bit string ends in \(\bs{1}\) or ends in \(\bs{0}\text{.}\)

28. Practice.

Consider the sequence \(a\) defined recursively by \(a_0= 3\text{,}\) \(a_1 =5\text{,}\) and \(a_n =2a_{n-1} -a_{n-2}\) for \(n \ge 2\text{.}\) Use the special case of strong mathematical induction Theorem 8.5.19 to prove that \(a_n = 2n+3\) for \(n \ge 0\text{.}\)
Check.
Hint: The inductive hypothesis is that \(a_{n-1}=2(n-1)+3\) and \(a_{n-2}=2(n-2)+3\text{.}\)

29. Understand.

For Activity 8.4.A, we defined proper bit strings. Use strong mathematical induction Theorem 8.5.17 to prove that if a proper bit string \(b\) of length \(n\) has exactly weight \(2k\text{,}\) then \(b\) begins with (at least) \(k\) \(\bs{1}\) s. Hint: In the inductive step, consider two cases based on if \(b\) ends in \(\bs{1}\) or ends in \(\bs{0}\text{.}\)

30. Understand.

Consider the sequence \(b_n\) defined recursively by \(b_0= 0\text{,}\) \(b_1 =2\text{,}\) and \(b_n =4b_{n-1} -4b_{n-2}\) for \(n \ge 2\text{.}\) Use the special case of strong mathematical induction Theorem 8.5.19 to prove that \(b_n = n2^n\) for \(n \ge 0\text{.}\)
Check.
Hint: Copy and edit the proof in Example 8.5.21. It is convenient to write \(4 = 2^2\text{.}\)

31. Understand.

Consider the sequence \(c\) defined recursively by \(c_0=3\text{,}\) \(c_1=20\text{,}\) and \(c_n=10c_{n-1} -25c_{n-2}\) for \(n \ge 2\text{.}\) Use the special case of strong mathematical induction Theorem 8.5.19 to prove that \(c_n=(n+3)5^n\) for \(n \ge 0\text{.}\)

32. Understand.

Consider the sequence \(a_n\) is defined by \(a_1=2\text{,}\) \(a_2=-3\text{,}\) and \(a_n=a_{n-2}+(-1)^{n+1}2\) for \(n\ge 3\text{.}\) We saw this sequence in Example 8.5.6. Use the special case of strong mathematical induction Theorem 8.5.19 to prove that \(a_n=(-1)^n(n+2)\) for \(n \ge 0\text{.}\)

33. Recap.

Do you know …
  1. What strong mathematical induction is?
  2. How to use the special case of strong mathematical induction to prove an explicit rule for a second order recursively-defined sequence?

34. Explore.

Our goal for this exercise is to prove an explicit formula for the Fibonacci sequence.
Write \(\alpha = \displaystyle \frac{1+\sqrt{5}}{2}\) and \(\beta = \displaystyle \frac{1-\sqrt{5}}{2}\text{.}\)
  1. Check that \(\alpha^2 = \alpha + 1\text{.}\) It turns out that \(\beta^2 = \beta + 1\text{,}\) but you are not asked to check that.
  2. Use the special case of strong mathematical induction Theorem 8.5.19 to prove Binet’s formula:
    \begin{equation*} F_n = \frac{1}{\sqrt{5}}\left(\alpha^n-\beta^n\right) \end{equation*}
    for \(n \ge 0\text{.}\) Hint: In the inductive step use that \(\alpha^{n-1}= \alpha \cdot \alpha^{n-2}\) and \(\beta^{n-1}= \beta \cdot \beta^{n-2}\text{.}\) When appropriate, factor out \(\alpha^{n-2}\) and \(\beta^{n-2}\text{.}\) Replace \(\alpha +1\) with \(\alpha^2\) and replace \(\beta + 1\) with \(\beta^2\text{.}\)
PrevTopNext