Sequences and Series · Lesson 4

Recursive rules and repeating patterns

A recursive rule gives a starting term and a rule that makes each term from the one before it. For a1=3a_1 = 3 and an=2an−1−1a_n = 2a_{n-1} - 1, double the previous term and subtract 1: a2=2⋅3−1=5a_2 = 2 \cdot 3 - 1 = 5, a3=9a_3 = 9, and so on. Write the terms in a short list and keep track of which term you are on.

Many patterns repeat in a cycle: the digits of 37=0.428571‾\frac{3}{7} = 0.\overline{428571}, the units digits of powers of 7 (7, 9, 3, 1), and the powers of ii (i,−1,−i,1i, -1, -i, 1). To find a far-off term, divide its position by the cycle length and use the remainder.

A remainder of rr points to the rrth item of the cycle. A remainder of 0 means the position ends a full cycle, so the answer is the last item of the cycle, not the first.

Common cycles
PatternCycleLength
Powers of ii: i1,i2,i3,i4i^1, i^2, i^3, i^4i,−1,−i,1i, -1, -i, 14
Units digits of 71,72,73,747^1, 7^2, 7^3, 7^47, 9, 3, 14
Units digits of 21,22,23,242^1, 2^2, 2^3, 2^42, 4, 8, 64
Digits of 37=0.428571428571…\frac{3}{7} = 0.428571428571\ldots4, 2, 8, 5, 7, 16

Worked example Easy

A sequence is defined by a1=3a_1 = 3 and an=2an−1−1a_n = 2a_{n-1} - 1 for n≥2n \geq 2. What is the value of a5a_5?

  1. 1717
  2. 1818
  3. 3333Answer
  4. 6565

How to solve it

  1. a2=2⋅3−1=5a_2 = 2 \cdot 3 - 1 = 5.
  2. a3=2⋅5−1=9a_3 = 2 \cdot 5 - 1 = 9.
  3. a4=2⋅9−1=17a_4 = 2 \cdot 9 - 1 = 17.
  4. a5=2⋅17−1=33a_5 = 2 \cdot 17 - 1 = 33.

Why each choice is right or wrong

  • A. Incorrect. 17 is a4a_4. One more step gives a5=2⋅17−1=33a_5 = 2 \cdot 17 - 1 = 33.
  • B. Incorrect. 18 reads the rule as 2(an−1−1)2(a_{n-1} - 1), giving 3, 4, 6, 10, 18. The rule doubles first and then subtracts 1.
  • C. Correct. The terms are 3, 5, 9, 17, 33, so a5=33a_5 = 33.
  • D. Incorrect. 65 is a6a_6. It comes from treating 3 as a0a_0 and computing five new terms; a1=3a_1 = 3 is already the first term.

Worked example Medium

The decimal form of 37\frac{3}{7} is 0.428571428571…0.428571428571\ldots, in which the six digits 428571 repeat without end. What is the 100th digit to the right of the decimal point?

  1. 22
  2. 55Answer
  3. 77
  4. 88

How to solve it

  1. The cycle 4, 2, 8, 5, 7, 1 has length 6.
  2. Divide the position by the cycle length: 100=6⋅16+4100 = 6 \cdot 16 + 4, so the remainder is 4.
  3. Sixteen full cycles end at the 96th digit, and the 100th digit is the 4th digit of the cycle: 5.

Why each choice is right or wrong

  • A. Incorrect. 2 divides by 7, the denominator, giving remainder 2. The cycle length is the number of repeating digits, 6.
  • B. Correct. 100=6⋅16+4100 = 6 \cdot 16 + 4, and the 4th digit of 428571 is 5.
  • C. Incorrect. 7 counts the cycle positions from 0, so remainder 4 lands on the 5th digit. Remainder 4 means the 4th digit.
  • D. Incorrect. 8 counts the 0 before the decimal point as the first digit, which shifts the position to the 99th decimal digit.

Trap A remainder of 0

If the position is a multiple of the cycle length, the remainder is 0 and the term is the last item of the cycle. The 52nd power of 7 ends a cycle of 4, so its units digit is 1, not 7.

Trap Starting the count at 0

Number the cycle 1, 2, 3, ... from its first item. If you number from 0, every answer shifts one place. Check with a small case: i1=ii^1 = i, and 1=4⋅0+11 = 4 \cdot 0 + 1 has remainder 1, the 1st item of the cycle i,−1,−i,1i, -1, -i, 1.

Calculator When a calculator isn’t faster

Hand work is faster here. A recursive rule takes a few lines, and a cycle question needs only one division. Your calculator can confirm a remainder (divide, keep the whole-number part, multiply back and subtract), but it cannot show the 100th digit of a decimal or the units digit of 7587^{58} directly, because those numbers are too long for the screen.