Skip to main content

Section 8.1 Recursively-defined Sequences

In Section 6.5, we looked at sequences defined by an explicit rule. Another way of defining a sequence uses a recursive rule in which each term is defined in terms of the previous term(s). In this section, we evaluate recursively-defined sequences and model with recursively-defined sequences. But first, we start with an activity.

Subsection 8.1.A The Towers of Hanoi

The puzzle we are about to do is famous. Do not look for information about it online — that will spoil the fun.

Activity 8.1.A Towers of Hanoi Puzzle.

  Given a disks of various diameters stacked in order on the first of three towers (pegs) as shown in Figure 8.1.2, it is only physically possible to lift the top disk up off any peg and put it down on another peg. Your goal is to move the entire tower of disks from the first tower to the third tower subject to two rules:
  • Rule 1: You may only move one disk at a time.
  • Rule 2: You may not put a larger disk on top of a smaller one.
Figure 8.1.2. The starting and end configurations for the Towers of Hanoi game.
  1. Play Towers of Hanoi. You can move a disk by clicking on it and dragging it to another peg. Solve the puzzle for three disks.
  2. Solve the puzzle for four disks without using the solve button.
  3. Now, use the solve button to solve the puzzle for four disks. Keep track of when and where the largest disk moves. Where are the other disks when it moves? Hint: The largest disk moves once.
  4. The minimum number of moves to solve the puzzle with three disks is seven. To solve the puzzle for four disks we need to move the top three disks, then the largest disk, and then we need to move the top three disks again. Explain why this strategy gives a solution to the puzzle with four disks in
    \begin{equation*} 7+1+7=15 \end{equation*}
    moves.
  5. Use the solve button to solve the puzzle for four disks again and look for the minimum number of moves.
  6. Generalize our strategy from (d) to guess how many moves it will take to solve the puzzle with five disks.
  7. Use the solve button to check your answer to (f).
  8. Consider the sequence \(h\) where \(h_n\) is the minimum number of moves needed to solve the puzzle with \(n\) disks for \(n \ge 1\text{.}\) The minimum number of moves needed to solve the puzzle with \(n-1\) disks would then be \(h_{n-1}\text{.}\) Make a conjecture about a rule for \(h_n\) in terms of \(h_{n-1}\text{.}\)
  9. We saw that \(h_3=7\text{,}\) \(h_4=15\text{,}\) and \(h_5=31\text{.}\) Use the solve button to calculate \(h_6\) and \(h_7\text{.}\)
  10. Based on the numbers from (i), make a conjecture about an explicit rule for \(h_n\text{.}\)
Let’s take a closer look at Activity 8.1.A.

Example 8.1.3 Tower of Hanoi puzzle.

Consider the sequence \(h\) where \(h_n\) is the minimum number of moves needed to solve the puzzle with \(n\) disks for \(n \ge 1\text{.}\) The minimum number of moves needed to solve the puzzle with \(n-1\) disks would then be \(h_{n-1}\text{.}\) Make a conjecture about a rule for \(h_n\) in terms of \(h_{n-1}\text{.}\)
Solution.
To solve the puzzle for \(n\) disks, we can break the process into three phases.
  • Phase 1: Relocate the top \(n-1\) disks in the pile to Tower 2. [\(h_{n-1}\) moves]
  • Phase 2: Move the largest disk to Tower 3. [1 move]
  • Phase 3: Relocate the top \(n-1\) disks in the pile to Tower 3. [\(h_{n-1}\) moves]
This analysis tells us that
\begin{equation*} h_n=2h_{n-1}+1\text{.} \end{equation*}

Subsection 8.1.B Recursively-defined Sequences

In Section 6.5, we worked with sequences that were defined explicitly, by a formula or in words. Let’s take a closer look at two of those sequences.

Example 8.1.4 First look at recursively-defined sequences.

 
  1. Consider the sequence \(a_n\) from Activity 6.5.A that was defined by \(a_n=10n+2\) for \(n\ge 0\text{.}\) The first few terms are
    \begin{equation*} 2, 12, 32, 42, 52, \ldots\text{.} \end{equation*}
    What do we notice about how each term is calculated from the previous term?
    Solution.
    Each term (\(a_n\)) is ten more than the previous term (\(a_{n-1}\)) . That is,
    \begin{equation*} 2 \xrightarrow[+ 10]{} 12 \xrightarrow[+ 10]{} 22 \xrightarrow[+ 10]{} 32 \xrightarrow[+ 10]{} 42 \xrightarrow[+ 10]{} 52\text{.} \end{equation*}
    Thus for \(n\ge 1\) we have
    \begin{equation*} a_n=a_{n-1}+10\text{.} \end{equation*}
  2. Consider the sequence \(b_i\) from Activity 6.5.A that was defined by \(b_i=2\cdot10^i\) for \(i\ge 0\text{.}\) The first few terms are
    \begin{equation*} 2, 20,200,2000,20000, \ldots\text{.} \end{equation*}
    What do we notice about how each term is calculated from the previous term?
    Solution.
    Each term (\(b_i\)) is ten times the previous term (\(b_{i-1}\)). That is,
    \begin{equation*} 2 \xrightarrow[\times 10]{} 20 \xrightarrow[\times 10]{} 200 \xrightarrow[\times 10]{} 2000 \xrightarrow[\times 10]{} 20000\text{.} \end{equation*}
    Thus for \(i\ge 1\) we have
    \begin{equation*} b_i=10b_{i-1} \end{equation*}
Let’s look at a sequence defined by such a rule.

Example 8.1.5 Double and add three.

Consider the sequence \(c\) is defined by the \(c_0=1\) and
\begin{equation*} c_k=2c_{k-1}+3 \end{equation*}
for \(k \ge 1\text{.}\) Note that the rule for this sequence is actually piecewise-defined
\begin{equation*} c_k = \left\{\begin{array}{cl} 1 \amp \text{ if } k=0 \\ 2c_{k-1}+3 \amp \text{ if } k\ge 1 \end{array} \right.\text{.} \end{equation*}
Also notice that the second part of the rule gives an infinite list of equations:
\begin{align*} (k=1:) \quad c_1\amp =2c_0+3\\ (k=2:) \quad c_2\amp =2c_1+3\\ (k=3:) \quad c_3\amp =2c_2+3\\ (k=4:) \quad c_4\amp =2c_3+3\\ \amp \vdots \end{align*}
It is often helpful to think of the rule in words: To get each term, we double the previous term and then add 3.
  1. Evaluate \(c_4\text{.}\)
    Solution.
    First recall that \(c_0=1\text{.}\) When \(k=1\) the rule tells us
    \begin{equation*} c_1=2c_0+3=2(1)+3=5\text{.} \end{equation*}
    Next, when \(k=2\) we get
    \begin{equation*} c_2=2c_1+3=2(5)+3=13\text{.} \end{equation*}
    When \(k=3\) we have
    \begin{equation*} c_3=2c_2+3=2(13)+3 = 29\text{.} \end{equation*}
    Finally, when \(k=4\) we find
    \begin{equation*} c_4=2c_3+3=2(29)+3=61\text{.} \end{equation*}
  2. Write an explicit rule for \(c_k\text{.}\)
    Solution.
    Since we are multiplying the previous term by 2 each time, it is reasonable to suspect that an explicit formula involves a power of 2. Table 8.1.6 compares the first five terms of \(c\) to the powers of 2. Since there is no obvious pattern with \(2^k\) we have listed \(2^{k+1}\) and then \(2^{k+2}\) as well. It looks like \(c_k\) is 3 smaller than \(2^{k+2}\) and so we conjecture that \(c_k=2^{k+2}-3\text{.}\)
    We can check that the definition gives \(c_5=2c_4+3=2(61)+3 = 125\) and our explicit formula gives \(c_5=2^{5+2}-3 = 128-3 = 125\text{.}\) We will see how to verify these conjectures in Section 8.2.
    Table 8.1.6. The terms of the sequence from Example 8.1.5 compared to the powers of 2
    \(k\) 0 1 2 3 4
    \(c_k\) 1 5 13 29 61
    \(2^k\) 1 2 4 8 16
    \(2^{k+1}\) 2 4 8 16 32
    \(2^{k+2}\) 4 8 16 32 64
We state the formal definitions.

Definition 8.1.7 Recursively-defined sequence.

 
  1. The first term (or first few terms) of a sequence is the initial condition(s). If a sequence \(a\) starts at \(s\) for some nonnegative integer \(s\text{,}\) then the initial condition is \(a_s\) (and perhaps subsequent terms such as \(a_{s+1}\text{,}\) \(a_{s+2}\text{,}\) etc.) For example, the initial condition for the sequence \(c\) defined in Example 8.1.5 was \(c_0=1\text{.}\)
  2. A recursion (or recursive rule) for a sequence specifies how each term (\(a_n\)) can be calculated from the previous term(s) (\(a_{n-1}\) and perhaps \(a_{n-2}\text{,}\) \(a_{n-3}\text{,}\) and so on). For example, the recursion for the sequence \(c\) defined in Example 8.1.5 was \(c_n=2c_{n-1}+3\text{.}\) A recursion may involve the index \(n\) as well as previous term(s). A recursion should use the previous term(s) in a nontrivial way. We do not consider explicitly-defined rules (that use the index but not previous terms) to be recursive.
  3. A sequence is recursively-defined if we are given a recursion and enough initial conditions to evaluate the recursion at all values. For example, the recursion for the sequence \(c\) defined in Example 8.1.5 starts at \(k=1\text{,}\) so we needed the initial condition to provide the value of \(c_0\text{.}\)
  4. A recursive rule that involves only one previous term is first order. For example, the sequence \(c\) defined in Example 8.1.5 is first-order.
Now it is your turn to work with recursively-defined sequences.

Activity 8.1.B Evaluating recursively-defined sequences.

 
  1. Evaluate the first four terms of the sequence defined by \(t_0=3\) and \(t_i=3t_{i-1}-5\) for \(i \ge 1\text{.}\)
  2. Evaluate \(v_3\) for the sequence defined by \(v_0=2\) and \(v_m=v_{m-1}^2-1\) for \(m \ge 1\text{.}\)
  3. Evaluate \(a_5\) for the sequence defined by \(a_1 = 5\) and \(a_n=a_{n-1}+2n\) for \(n\ge 2\text{.}\) Note that the recursion involves the index \(n\text{.}\) For example, when \(n=2\) we get \(a_2=a_1+2(2)=5+4=9\) and when \(n=3\) we have \(a_3=a_2+2(3)=9+6=15\text{.}\)
  4. Evaluate \(b_4\) for the sequence defined by \(b_1=1\) and \(b_k=kb_{k-1}\) for \(k \ge 2\text{.}\) What do you notice? Write an explicit formula for \(b_k\text{.}\)
  5. Evaluate \(c_4\) for the sequence defined by \(c_0=0\) and \(c_i=c_{i-1}+i\) for \(i \ge 1\text{.}\) What do you notice? Write an explicit formula for \(c_i\text{.}\) Hint: Handshakes.
As we saw in Activity 8.1.B, a recursion can involve the index. Let’s look at some similar examples.

Example 8.1.9 Evaluating recursively-defined sequences that involve the index.

 
  1. Evaluate \(d_5\) for the sequence defined by \(d_1 = 1\) and \(d_n=d_{n-1}+2n-1\) for \(n\ge 2\text{.}\) What do you notice? Write an explicit formula for \(d_n\text{.}\)
    Solution.
    When \(n=2\text{,}\) we have \(d_2=d_1+2(2)-1=1+3=4\text{.}\)
    When \(n=3\text{,}\) we have \(d_3=d_2+2(3)-1=4+5=9\text{.}\)
    When \(n=4\text{,}\) we have \(d_4=d_3+2(4)-1=9+7=16\text{.}\)
    When \(n=5\text{,}\) we have \(d_5=d_4+2(5)-1=16+9 = 25\text{.}\)
    Notice \(d_1=1 = 1^2\text{,}\) \(d_2=4=2^2\text{,}\) \(d_3=9=3^2\text{,}\) \(d_4=16=4^2\text{,}\) and \(d_5=25=5^2\text{.}\)
    We conjecture that \(d_n=n^2\) for \(n \ge 1\text{.}\)
  2. Evaluate \(s_4\) for the sequence defined by \(s_1=10\) and \(s_k=ks_{k-1}\) for \(k \ge 2\text{.}\) What do you notice? Write an explicit formula for \(b_k\text{.}\)
    Solution.
    When \(k=2\text{,}\) we have \(s_2=sb_1 = 2(10) = 20\text{.}\)
    When \(k=3\text{,}\) we have \(s_3=3s_2 = 3(20) = 60\text{.}\)
    When \(k=4\text{,}\) we have \(s_4=4s_3 = 4(60) = 240\text{.}\)
    Notice that \(s_1=10=10(1!)\text{,}\) \(s_2=20=10(2!)\text{,}\) \(s_3=60=10(3!)\text{,}\) and \(s_4=240=10(4!)\text{.}\)
    We conjecture that \(s_k=10(k!)=10k!\)
  3. Evaluate \(t_4\) for the sequence defined by \(t_0=0\) and \(t_i=t_{i-1}+2i\) for \(i \ge 1\text{.}\) What do you notice? Write an explicit formula for \(t_i\text{.}\) Hint: Factor.
    Solution.
    When \(i=1\text{,}\) we have \(t_1=t_0+2(1) = 0+2=2\text{.}\)
    When \(i=2\text{,}\) we have \(t_2=t_1+2(2) = 2+4=6\text{.}\)
    When \(i=3\text{,}\) we have \(t_3=t_2+2(3) = 6+6=12\text{.}\)
    When \(i=4\text{,}\) we have \(t_4=t_3+2(4) = 12+8=20\text{.}\)
    Notice that \(t_0=0=(0)(1)\text{,}\) \(t_1=2=(1)(2)\text{,}\) \(t_2=6=(2)(3)\text{,}\) \(t_3=12=(3)(4)\text{,}\) and \(t_4=20=(4)(5)\text{.}\)
    We conjecture that \(t_i=i(i+1)\) for \(i \ge 0\text{.}\)

Subsection 8.1.C Modeling with Recursively-defined Sequences

In the examples we have seen so far, we have gone from a sequence defined recursively to a list of terms or explicitly-defined rule. It is particularly useful to go the opposite direction, from a list or explicitly-defined rule to a recursively-defined sequence. Let’s try modeling with such sequences.

Example 8.1.10 Write the recursive rule for sequence from list.

 
  1. Write a simple recursive rule that generates a sequence \(a\) that begins
    \begin{equation*} 5, 6, 7, 8, 9, 10, \ldots \end{equation*}
    Solution.
    To get from each term to the next we add 1. That is,
    \begin{equation*} 5 \xrightarrow[+ 1]{} 6 \xrightarrow[+ 1]{} 7 \xrightarrow[+ 1]{} 8 \xrightarrow[+ 1]{} 9 \xrightarrow[+ 1]{} 10\text{.} \end{equation*}
    Thus \(a_0=5\) and \(a_n=a_{n-1}+1\) for \(n \ge 1\text{.}\) By the way, an explicit rule for this sequence is \(a_n=n+5\) for \(n\ge 0\text{.}\)
  2. Write a simple recursive rule that generates a sequence \(b_n\) defined by \(b_n=(n+1)(2n+1)\) for \(n \ge 0\text{.}\) Hint: The recursive definition depends on the index as well as the previous term.
    Solution.
    Let’s find the first few terms of \(b\text{.}\) We get \(b_0 = (1)(1) = 1\text{,}\) \(b_1 = (2)(3) = 6\text{,}\) \(b_3 = (4)(7) = 28\text{,}\) \(b_4 = (5)(9) = 45\text{,}\) and \(b_5 = (6)(11) = 66\text{.}\) That is, the sequence \(b\) begins
    \begin{equation*} 1, 6, 15, 28, 45, 66, \ldots \end{equation*}
    Look at what we add to get each term from the previous term:
    \begin{equation*} 1 \xrightarrow[+ 5]{} 6 \xrightarrow[+ 9]{} 15 \xrightarrow[+ 13]{} 28 \xrightarrow[+ 17]{} 45 \xrightarrow[+ 21]{} 66\text{.} \end{equation*}
    The values we are adding
    \begin{equation*} 5,9,13,17,21,\ldots \end{equation*}
    appear to depend on the index. An explicit rule for these terms we are adding is \(4n+1\) for \(n \ge 1\text{.}\) A recursive rule is \(b_0=1\) and
    \begin{equation*} b_n=b_{n-1}+4n+1 \end{equation*}
    for \(n \ge 1\text{.}\)
Try writing recursive definitions.

Activity 8.1.C Modeling with recursively-defined sequences.

Write a simple recursive rule that generates each sequence. Make sure you state where the index starts and include the initial condition. Start your indexing at 0 or 1 (your choice).
  1. \(\displaystyle 1, 6, 11, 16, 21, \ldots\)
  2. \(\displaystyle 2, -10, 50, -250, 1250,\ldots\)
  3. \(\displaystyle 2, \frac{1}{2}, 2, \frac{1}{2}, 2, \frac{1}{2}, \ldots\)
  4. \(\displaystyle 5, 10, 30, 120, 600, \ldots\)
  5. \(5, 9, 17, 33, 65, 129, \ldots\text{.}\) Write a recursion that does not involve the index.
  6. \(5, 9, 17, 33, 65, 129, \ldots\text{.}\) Now write a recursion that involves the index.
Check.
  1. Hint: What constant do we add to get the next term?
  2. Hint: What constant do we multiply by to get the next term?
  3. Hint: There are several ways to answer this question. One method is to alternatively add or subtract. To get the alternation, try \((-1)^n\) Another (easier?) method comes from realizing \(2=\frac{2}{1}\) and answering the question: ``How are \(\frac{2}{1}\) and \(\frac{1}{2}\) related?’’
  4. Hint: What do we multiply by to get from each term to the next? Write a recursion that involves the index.
  5. Hint: The recursion begins by doubling the previous term.
  6. Hint: Make sure your answer involves the index.
Let’s look at more examples writing the recursion from a list.

Example 8.1.12 Modeling with recursively-defined sequences.

Write a simple recursive rule that generates each sequence. Make sure you state where the index starts and include the initial condition. Start your indexing at 0 or 1 (your choice).
  1. \(3, 6, 18, 72, 360, \ldots\) Write a recursion that involves the index.
    Solution.
    Look at what we multiply by to get each term from the previous term:
    \begin{equation*} 3 \xrightarrow[\times 2]{} 6 \xrightarrow[\times 3]{} 18 \xrightarrow[\times 4]{} 72 \xrightarrow[\times 5]{} 360\text{.} \end{equation*}
    If we set \(a_1=3\text{,}\) then \(a_2=6 =2(3)=2a_1\text{,}\) \(a_3=18 =3(6)=3a_2\text{,}\) \(a_4=72 =4(18)=4a_3\text{,}\) and \(a_5=360 =5(72)=5a_4\text{.}\)
    We conjecture that \(a_1=\) and \(a_n=na_{n-1}\) for \(n \ge 2\text{.}\)
  2. \(4, 7, 13, 25, 49, 97, \ldots\text{.}\) Write a recursion that does not involve the index. Hint: The recursion begins by doubling the previous term.
    Solution.
    Let’s set \(b_0 = 4\text{.}\) Notice that \(b_1=7 = 2(4)-1=2b_0-1\text{,}\) \(b_2=13 = 2(7)-1=2b_1-1\text{,}\) \(b_3=25 = 2(13)-1=2b_2-1\text{,}\) \(b_4=49 = 2(25)-1=2b_3-1\text{,}\) and \(b_5=97 = 2(49)-1=2b_4-1\text{.}\) We conjecture that \(b_0 = 4\) and \(b_n=2b_{n-1}-1\) for \(n \ge 1\text{.}\)
  3. \(4, 7, 13, 25, 49, 97, \ldots\text{.}\) Now write a recursion that involves the index.
    Solution.
    Look at what we add to get each term from the previous term:
    \begin{equation*} 4 \xrightarrow[+ 3]{} 7 \xrightarrow[+ 6]{} 13 \xrightarrow[+ 12]{} 25 \xrightarrow[+ 24]{} 49 \xrightarrow[+ 48]{} 97\text{.} \end{equation*}
    The terms we added are \(3, 6, 12, 24, 48, \ldots\text{.}\) Each integer we added is twice the previous integer, so an explicit form is \(3\cdot 2^n\) for \(n \ge 0\text{.}\) That is, we have
    \begin{equation*} 4 \xrightarrow[+ 3\cdot 2^0]{} 7 \xrightarrow[+ 3\cdot 2^1]{} 13 \xrightarrow[+ 3\cdot 2^2]{} 25 \xrightarrow[+ 3\cdot 2^3]{} 49 \xrightarrow[+ 3\cdot 2^4]{} 97\text{.} \end{equation*}
    Thus, we have \(b_0=4\text{,}\) \(b_1 = 7 = 4+ 3\cdot 2^0\text{,}\) \(b_2 = 13 = 7+ 3\cdot 2^1\text{,}\) \(b_3 = 25 = 13+ 3\cdot 2^2\text{,}\) \(b_4 = 49 = 25+ 3\cdot 2^3\text{,}\) and \(b_5 = 97 = 49+ 3\cdot 2^4\text{.}\)
    We conjecture that \(b_0=4\) and \(b_n=b_{n-1}+3\cdot2^{n-1}\) for \(n \ge 1\text{.}\)

Subsection 8.1.D Exercises

Subsubsection Exercises for 8.1.A The Towers of Hanoi

1. Practice.

 
  1. Use the recursion from Example 8.1.3 to calculate the minimum number of moves needed to solve the Tower of Hanoi puzzle with 2, 3, 4, 5, 6, 7, 8 disks. Hint: It takes one move to solve the puzzle with one disk.
  2. Watch the solution for eight disks by entering 8 and clicking Solve. Does the minimum number of moves agree with your answer to 1.(a)?
  3. What is the minimum number of moves needed to solve the Tower of Hanoi puzzle with nine disks? Explain how to use the recursion to answer.
Check.
  1. Hint: The terms are \(1, 3, 7, \ldots, 255\text{.}\)
  2. Yes
  3. Hint: Use the recursion from Example 8.1.3.

2. Understand.

Let \(h_n\) be the minimum number of moves needed to solve the Tower of Hanoi puzzle with \(n\) disks.
  1. List the first eight terms of \(h_n\) from our work on Activity 8.1.A or Exercise 1.
  2. Conjecture an explicit formula for \(h_n\text{.}\)
  3. Use the explicit formula to calculate \(h_9\) and \(h_{10}\text{.}\)
Check.
  1. Hint: Same list as in Exercise 1.
  2. Hint: Since we are doubling, the explicit formula likely involves \(2^n\text{.}\)
  3. Hint: \(h_{10} = 1023\text{.}\)

3. Understand.

Use the phases discussed in Example 8.1.3 to explain why there exists a solution to the Tower of Hanoi puzzle for any number of disks.

4. Understand.

In the Tower of Hanoi puzzle, label the towers 1, 2, and 3. An arrangement of \(n\) disks can be represented by the \(n-tuple\)
\begin{equation*} (a_1,a_2,\ldots, a_{n-1}, a_n) \end{equation*}
where \(a_1\) is the tower number of the largest disk, \(a_2\) is the tower number of the next largest disk, …, \(a_{n-1}\) is the tower number of the next-to-smallest disk, and \(a_n\) is the tower number of the smallest disk. In this notation, the starting state is \((1,1,\ldots, 1,1)\) and the ending state is \((2,2,\ldots, 2,2)\text{.}\)
  1. Represent the state in Figure 8.1.17 with a 5-tuple.
    Figure 8.1.17. A state of the Tower of Hanoi puzzle with five disks.
  2. List the states in a minimal solution of the Tower of Hanoi with three disks.
  3. How many possible states are there in the Tower of Hanoi with three disks? Explain how you counted.
  4. Explain why each tuple uniquely determines a state. That is, this representation is a pairing between the states of the Tower of Hanoi puzzle and the elements of \(\{1,2,3\}^3\text{.}\)
Check.
  1. \(\displaystyle (1,1,3,2,1)\)
  2. Hint: The list is \((1,1,1), (1,1,3), \ldots, (3,3,3)\text{.}\)
  3. Hint: There is a state for each element of \(\{1,2,3\}^3\text{.}\)
  4. Hint: On any tower, the disks can only be stacked from largest on the bottom to smallest on the top.

5. Explore.

In this problem we introduce the graph of Hanoi. \(H_3\) which has a vertex for each possible state. As we saw in Exercise 4, each state corresponds to a unique \(3\)-tuple in \(\{1,2,3\}^3\text{.}\) There is an edge between two vertices in \(H_33\) if we can move between those two states with a single move in the puzzle. For example, there is an edge between \((1,1,1)\) and \((1,1,2)\) corresponding to moving the smallest disk from tower 1 to tower 2 and there is an edge between \((1,2,2)\) and \((3,2,2)\) corresponding to moving the largest disk from tower 1 to tower 3 (which is possible because the other two disks are on tower 2). Draw \(H_3\text{.}\) Be sure to label the vertices.

Subsubsection Exercises for 8.1.B Recursively-defined Sequences

6. Practice.

Evaluate the first six terms of each sequence. Your list should begin with the initial condition.
  1. \(p_0= 10\) and \(p_m = p_{m-1} + 3\) for \(m \ge 1\text{.}\)
  2. \(q_0= 10\) and \(q_n = 3q_{n-1}\) for \(n \ge 1\text{.}\)
  3. \(r_0= 10\) and \(r_k = r_{k-1}^2\) for \(k \ge 1\text{.}\)
Check.
  1. Hint: The terms are \(10, 13, \ldots, 25\text{.}\)
  2. Hint: The terms are \(10, 30, \ldots\text{.}\)
  3. Hint: The terms are \(10, 100, \ldots\text{.}\)

7. Practice.

Evaluate the indicated term of each sequence.
  1. Evaluate \(u_6\) where \(u_1= 3\) and \(u_i = u_{i-1}+1\) for \(i \ge 2\text{.}\)
  2. Evaluate \(v_4\) where \(v_1= 1\) and \(v_n = 2v_{n-1}-1\) for \(n \ge 2\text{.}\)
  3. Evaluate \(w_3\) where \(w_1= 2\) and \(w_j = (w_{j-1}+1)^2\) for \(j \ge 2\text{.}\)
Check.
  2. Hint: The sequence is constant.
  3. 100

8. Practice.

Evaluate the first six terms of each sequence. Your list should begin with the initial condition. Notice that the rule uses the index as well as the previous term.
  1. \(a_1= 2\) and \(a_j = ja_{j-1}\) for \(j \ge 2\text{.}\)
  2. \(b_1= 1\) and \(b_n = b_{n-1}+n\) for \(n \ge 2\text{.}\)
  3. \(c_1= 1\) and \(c_m = c_{m-1}+2m-1\) for \(m \ge 2\text{.}\)
Check.
  1. Hint: The terms are \(2, 4, \ldots, 1440\text{.}\)
  2. Hint: The terms are \(1, 3, \ldots\text{.}\)
  3. Hint: The terms are \(1, 4, \ldots\text{.}\)

9. Practice.

Evaluate the indicated term of each sequence. Notice that the rule uses the index as well as the previous term.
  1. Find \(x_4\) where \(x_0= 1\) and \(x_i = ix_{i-1}+1\) for \(i \ge 1\text{.}\)
  2. Find \(y_4\) where \(y_0= 1\) and \(y_k = 2y_{k-1}+k\) for \(k \ge 1\text{.}\)
  3. Find \(z_3\) where \(z_0= 1\) and \(z_n = z_{n-1}+2n\) for \(n \ge 1\text{.}\)
Check.
  1. Hint: \(x_2=3\text{.}\)
  2. Hint: \(y_2=3\text{.}\)
  3. Hint: \(z_2=3\text{.}\)

10. Understand.

Make a reasonable conjecture about an explicit rule for each sequence from Exercise 6.
Check.
  1. Hint: Since we are repeatedly adding three, the explicit formula involves \(3m\text{.}\)
  2. Hint: Since we are repeatedly multiplying by three, the explicit formula involves \(3^n\text{.}\)
  3. Hint: The formula is a power of 10, but not just \(10^k\text{.}\)

11. Understand.

Make a reasonable conjecture about an explicit rule for each sequence from Exercise 7.

12. Recap.

Do you know …
  1. What we call a rule that defines each term of a sequence using previous terms of the sequence?
  2. How to evaluate recursively-defined sequences?
  3. Why you need an initial condition to define a recursively-defined sequence?

Subsubsection Exercises for 8.1.C Modeling with Recursively-defined Sequences

13. Practice.

Write the initial condition and a simple recursive rule for each sequence. Start your indexing at 0 or 1 (your choice).
  1. \(\displaystyle 5, 7, 9, 11, 13, \ldots\)
  2. \(\displaystyle 0.1, 0.01, 0.001, 0.0001, \ldots\)
  3. \(\displaystyle 5, -5, 5, -5, 5, -5, \ldots\)
Check.
  1. \(a_0=5\) and \(a_n=a_{n-1}+2\) for \(n \ge 1\text{.}\)
  2. Hint: We are multiplying by 0.1.
  3. Hint: We are multiplying by -1.

14. Practice.

Write the initial condition and a simple recursive rule for each sequence. Hint: Start by listing the first six terms.
  1. \(a_n = 5n\) for \(n \ge 0\text{.}\)
  2. \(b_n=5n+1\) for \(n \ge 0\text{.}\)
  3. \(c_n=5n-1\) for \(n \ge 0\text{.}\)
  4. \(s_m = 2^m\) for \(m \ge 0\text{.}\)
  5. \(t_m = 3\cdot 2^m\) for \(m \ge 0\text{.}\)
  6. \(u_m = \frac{3}{2^m}\) for \(m \ge 0\text{.}\)
Check.
  1. \(a_0=0\) and \(a_n=a_{n-1}+5\) for \(n \ge 1\text{.}\)
  2. Hint: Same recursion as 14.(a) but different initial condition.
  3. Hint: Same recursion as 14.(a) but different initial condition.
  4. Hint: The first six terms are \(1, 2, 4, 8, 16, 32\text{.}\)
  5. Hint: Same recursion as 14.(d) but different initial condition.
  6. : Hint: We are dividing by two.

15. Practice.

Write the initial condition and a simple recursive rule for each sequence. Hint: Start by listing the first six terms.
  1. \(d_n = 2n+3\) for \(i \ge 1\text{.}\)
  2. \(h_k = 2^k\) for \(i \ge 1\text{.}\)
  3. \(w_i = i\) for \(i \ge 1\text{.}\)
  4. \(v_m = 4\) for \(m \ge 1\text{.}\)
  5. \(z_j = (-1)^j\) for \(k \ge 1\text{.}\)
Check.
  1. Hint: Adding two.
  2. Hint: Multiplying by two.
  3. Hint: We are adding a constant.
  4. Hint: Describe how each term is related to the previous term.
  5. Hint: We are multiplying by a constant.

16. Understand.

Consider a sequence \(a\) beginning
\begin{equation*} 3, 4, 6, 10, 18, 34, 66, \ldots \end{equation*}
  1. Write a simple explicit rule generating this sequence. Start your indexing at 0.
  2. Write the initial condition and a simple recursive rule for this sequence that involves the previous term and the index.
  3. Write the initial condition and a simple recursive rule for this sequence that does not involve the index.
Check.
  1. Hint: Handshakes.
  2. Hint: \(a_0=3\) and the recursion adds one, then adds two, then adds three, etc.
  3. Hint: The recursion begins by doubling the previous term.

17. Understand.

Consider a sequence \(b\) beginning
\begin{equation*} 11, 101, 1001, 10001, \ldots \end{equation*}
  1. Write a simple explicit rule generating this sequence. Start your indexing at 1.
  2. Write the initial condition and a simple recursive rule for this sequence that involves the previous term and the index.
  3. Write the initial condition and a simple recursive rule for this sequence that does not involve the index.
Check.
  1. Hint: Compare to the powers of 10.
  2. Hint: \(b_1=11\text{.}\) Calculate what we are adding to get from each term to the next.
  3. Hint: The recursion begins by multiplying the previous term by ten.

18. Understand.

Write the initial condition and a simple recursive rule for each sequence. Start your indexing at 0 or 1 (your choice). Hint: The recursion involves the index as well as the previous term.
  1. \(\displaystyle 3, 4, 6, 9, 13, 18, \ldots\)
  2. \(\displaystyle 2, 5, 10, 17, 26, 37, \ldots\)
Check.
  1. Hint: The recursion adds one, then adds two, then adds three, etc.
  2. Hint: The recursion adds three, then adds five, then adds seven, etc.

19. Understand.

Write the initial condition and a simple recursive rule for each sequence. Hint: The recursion involves the index as well as the previous term. Start by listing the first six terms.
  1. \(a_k = 5k!\) for \(k \ge 1\text{.}\)
  2. \(b_k = \frac{1}{k!}\) for \(k \ge 1\text{.}\)
  3. \(c_n = n(n-1)\) for \(n \ge 1\text{.}\)
  4. \(d_m = m(2m+1)\) for \(m \ge 0\text{.}\)
Check.
  1. Hint: To get from each term to the next, we multiply by \(k\text{.}\)
  2. Hint: To get from each term to the next, we divide by \(k\text{.}\) Use a fraction.
  3. Hint: To get from each term to the next, we add two, then add four, then add six, etc.
  4. Hint: To get from each term to the next, we add three, then add seven, then add eleven, etc.

20. Recap.

Do you know …
  1. How to model with recursively-defined sequences?
  2. How to write a recursion that for linear, exponential, handshakes, or factorials?

21. Explore.

 
  1. We deposit \(10,000\) into a bank account that earns 3% interest annually. Write \(a_n=\) the account balance at the end of \(n\) years. Note that interest is paid at the end of each year. Calculate \(a_0\text{,}\) \(a_1\text{,}\) and \(a_2\) and write a recursive rule for \(a_n\text{.}\) Simplify your answer using \(1 + .03 = 1.03\text{.}\) Note: you might know an explicit rule, but this question asks for a recursive rule, so \(a_{n-1}\) should be involved in your answer.
  2. As before, we deposit \(10,000\) into a bank account that earns 3% interest annually but then we deposit another \(10,000\) at the end of each year. Write \(b_n=\) the account balance at the end of \(n\) years. Note that interest is paid at the end of each year before we deposit the additional \(10,000\text{.}\) Calculate \(b_0\text{,}\) \(b_1\text{,}\) and \(b_2\) and write a recursive rule for \(b_n\text{.}\) Simplify your answer using \(1 + .03 = 1.03\text{.}\)
PrevTopNext