Recurrences and arithmetic · Definition

Recurrence relation

discrete mathematicsrecurrences

Before you start you need to know

Many counting problems are solved by describing how a large case is built from smaller ones, and that is exactly a recurrence.

Definition

A recurrence relation is an equation that expresses each term \(a_n\) of a sequence in terms of the previous \(k\) terms; with initial values, it determines the whole sequence.

\[a_n=f(a_{n-1},a_{n-2},\dots,a_{n-k})\]

A recurrence has two parts that must go together: the rule that computes \(a_n\) from earlier terms and the initial conditions that start the sequence. Without initial conditions infinitely many sequences satisfy the same rule; with them, the sequence is determined and can be computed step by step. The number of initial values needed is the order \(k\) of the recurrence, the number of earlier terms the rule uses.

Modeling a problem means reasoning about the last step. In the Tower of Hanoi, moving \(n\) disks requires moving \(n-1\), moving the largest and moving \(n-1\) again: \(T_n=2T_{n-1}+1\). With \(n\) lines in general position, the new line crosses the previous \(n-1\) and creates \(n\) new regions: \(R_n=R_{n-1}+n\). Binary strings with no two consecutive zeros end in 1 or in 10, which gives \(a_n=a_{n-1}+a_{n-2}\).

Computing the first terms often suggests a closed formula, such as \(T_n=2^n-1\) or \(R_n=1+n(n+1)/2\), confirmed by mathematical induction: check the base case and use the recurrence in the inductive step. A common mistake is to forget that the rule may start at \(n=1\) or \(n=2\) depending on the order, and that initial values do not come from the rule. A systematic method for solving linear recurrences comes later.

Think about it

How many sequences satisfy \(a_n=a_{n-1}+a_{n-2}\) when no initial conditions are fixed?

Infinitely many: each pair of values \((a_0,a_1)\) produces a different sequence.

Prove by induction that \(T_n=2^n-1\) satisfies \(T_n=2T_{n-1}+1\) with \(T_0=0\).

Base case: \(T_0=2^0-1=0\). Step: if \(T_{n-1}=2^{n-1}-1\), then \(T_n=2(2^{n-1}-1)+1=2^n-1\).

Exercises 10

  1. Let \(a_0=2\) and \(a_n=3a_{n-1}-1\) for \(n\ge1\). What is \(a_4\)?
  2. Let \(a_0=a_1=1\) and \(a_n=a_{n-1}+a_{n-2}\). What is \(a_6\)?
  3. Let \(a_0=1\) and \(a_n=a_{n-1}+2n\). What is \(a_5\)?
  4. If \(a_0=3\) and \(a_n=2a_{n-1}\), which is a formula for \(a_n\)?
  5. In the Tower of Hanoi, the minimum number of moves satisfies \(T_n=2T_{n-1}+1\) with \(T_0=0\). What is \(T_6\)?
  6. How many initial values are needed to determine a sequence with \(a_n=a_{n-1}+a_{n-2}\)?
  7. Let \(a_n\) be the number of binary strings of length \(n\) with no two consecutive zeros. It satisfies \(a_n=a_{n-1}+a_{n-2}\) with \(a_1=2\) and \(a_2=3\). What is \(a_5\)?
  8. The sequence with \(a_0=1,\ a_1=3\) and \(a_n=2a_{n-1}-a_{n-2}\) satisfies which formula?
  9. With \(n\) lines in general position, the number of regions of the plane satisfies \(R_n=R_{n-1}+n\) and \(R_0=1\). What is \(R_6\)?
  10. Let \(a_0=1\) and, for \(n\ge1\), \(a_n=a_0+a_1+\cdots+a_{n-1}\). What is \(a_6\)?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §8.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §5.6
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §10.1