A recursion rule

A recursion rule defines a sequence in two parts:

• a starting condition – the first term, for example $\displaystyle {a_1}={3}$;
• the rule – how each term is worked out from the term before it, for example $\displaystyle {a_{n+1}}={2a_n-1}$.

From the rule the terms come one after another:

• $\displaystyle {a_2}={2\cdot3-1}={5}$;
• $\displaystyle {a_3}={2\cdot5-1}={9}$;
• $\displaystyle {a_4}={2\cdot9-1}={17}$.

A computer works out a sequence defined by a recursion rule the same way: step by step, each step from the result of the step before.

With a formula by place, write $\displaystyle a_{n+1}$ and look for $\displaystyle a_n$ in it. In the sequence $\displaystyle {a_n}={n^2}$:

• The rule: $\displaystyle {a_1}={1}$, $\displaystyle {a_{n+1}}={a_n+2n+1}$.
• The rule has a meaning: each square is greater than the square before it by the odd number $\displaystyle 2n+1$.

The other way, from a recursion rule to a formula by place, is usually hard, and sometimes there is no simple formula at all. Sometimes it can be guessed from the terms.

In the sequence $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={2a_n-1}$ the terms are $\displaystyle 3, 5, 9, 17, 33, \ldots$

• Each term is 1 more than a power of 2: $\displaystyle {3}={2+1}$, $\displaystyle {5}={4+1}$, $\displaystyle {9}={8+1}$.
• The guess: $\displaystyle {a_n}={2^n+1}$.
• A guess that fits the first five terms is not a proof that it fits them all. The proof comes with mathematical induction, later in the course.

In the sequence $\displaystyle {a_1}={2}$, $\displaystyle {a_{n+1}}={\frac{1}{1-a_n}}$:

• $\displaystyle {a_2}={\frac{1}{1-2}}={-1}$;
• $\displaystyle {a_3}={\frac{1}{1-(-1)}}={\frac{1}{2}}$;
• $\displaystyle {a_4}={\frac{1}{1-\frac{1}{2}}}={2}={a_1}$.

$\displaystyle a_4$ is $\displaystyle a_1$ again, so from here the rule gives the same terms again: $\displaystyle 2, -1, \frac{1}{2}, 2, -1, \frac{1}{2}, \ldots$ This is a periodic sequence, and its period is 3.

• $\displaystyle a_{100}$: $\displaystyle {100}={3\cdot33+1}$, that is, after 33 whole periods we reach the first place of a period: $\displaystyle {a_{100}}={a_1}={2}$.
• The sum of the first 99 terms: 33 periods, each with the sum $\displaystyle {2-1+\frac{1}{2}}={1.5}$, so $\displaystyle {33\cdot1.5}={49.5}$.

A recursion rule can use the two terms before a term. Then it needs two starting conditions.

• The Fibonacci sequence: $\displaystyle {a_1}={1}$, $\displaystyle {a_2}={1}$, $\displaystyle {a_{n+2}}={a_{n+1}+a_n}$.
• Each term is the sum of the two terms before it: $\displaystyle 1, 1, 2, 3, 5, 8, 13, 21, \ldots$

A sequence is defined by the recursion rule $\displaystyle {a_1}={5}$, $\displaystyle {a_{n+1}}={a_n+2n}$.
Calculate $\displaystyle a_4$.

The sequence: $\displaystyle {a_n}={3n-1}$.

Simplify $\displaystyle a_{n+1}-a_n$.

Write a recursion rule for the sequence.

The sequence: $\displaystyle {a_n}={n^2+n}$.
Write $\displaystyle a_{n+1}$ as $\displaystyle a_n$ plus an expression in $\displaystyle n$, and write a recursion rule for the sequence.

A sequence is defined by the recursion rule $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={\frac{a_n+1}{a_n-1}}$.

Calculate $\displaystyle a_2$, $\displaystyle a_3$ and $\displaystyle a_4$. What can be said about the sequence?

What is $\displaystyle a_{51}$?

Calculate the sum of the first 20 terms.

In the picture of the squares from the lesson before, stage $\displaystyle n$ has $\displaystyle {a_n}={4n}$ shaded squares.
Write a recursion rule for $\displaystyle a_n$, and explain it with the picture.