audio read-through Introduction to Recursion and Sequences

Welcome to the first lesson in Topics in Algebra II!

DEFINITION sequence; notation for sequences
A sequence is an ordered list of numbers.

Each number in the sequence is called a term.

The $\,n^{\text{th}}\,$ term can be denoted as:

  • $\,u_n\,$ (subscript notation); or
  • $\,u(n)\,$ (function notation)

Examples

The first five terms of the sequence defined by $\,u(n) = n^2\,$ are: $$ \begin{align} &\cssId{s10}{u(1) = 1^2 = 1}\cr &\cssId{s11}{u(2) = 2^2 = 4}\cr &\cssId{s12}{u(3) = 3^2 = 9}\cr &\cssId{s13}{u(4) = 4^2 = 16}\cr &\cssId{s14}{u(5) = 5^2 = 25} \end{align} $$
The $\,27^{\text{th}}\,$ term of the sequence defined by $\,u_n = n + 3\,$ is: $$ \cssId{s16}{u_{27} = 27 + 3 = 30} $$
DEFINITION recursion
Recursion is a process in which each step of a pattern is dependent on the step or steps that came before it.
DEFINITION recursive formula
A recursive formula must specify:
  • one (or more) starting terms
  • a recursive rule that defines the $\,n^{\text{th}}\,$ term in relation to previous term(s)

Example

The recursive rule $$ \begin{align} &\cssId{s27}{u_1 = 2}\cr &\cssId{s28}{u_n = u_{n-1} + 3\ \ \text{for}\ \ n\ge 2} \end{align} $$ generates the sequence  $\,2\,,$ $\,5\,,$ $\,8\,,$ $\,11\,,$ $\,14\,,$ $\,\ldots\,$

Thought process:

  • Start with the number $\,2\,$:  $\,u_1=2\,$ tells you this; $\,u_1\,$ represents the first term in the sequence $\,u\,.$
  • To find any other term, take the previous term and add $\,3\,$:  $\,u_n = u_{n-1} + 3\,$ for $\,n\ge 2\,$ tells you this.

    For example, suppose $\,n = 2\,,$ so you're looking at: $$\cssId{s38}{u_2 = u_{2-1} + 3 = u_1 + 3}$$ How do you get the second term, $\,u_2\,$? Answer: take the first term, $\,u_1\,,$ and add $\,3\,$ to it.

Example

The recursive rule $$ \begin{align} &\cssId{s43}{w_1 = 1\,,\ \ \ w_2 = 1}\cr &\cssId{s44}{w_n = w_{n-1} + w_{n-2}\ \ \text{for}\ \ n\ge 3} \end{align} $$ generates the sequence  $\,1\,,$ $\,1\,,$ $\,2\,,$ $\,3\,,$ $\,5\,,$ $\,8\,,$ $\,13\,,$ $\,\ldots$

Thought process:

Start with the numbers $\,1\,$ and $\,1\,.$ To find any other term, take the previous two terms and add them together.

Defining a Sequence Both Recursively and Nonrecursively

Some sequences can be defined both recursively and non-recursively. For example, the sequence $$\cssId{s54}{3\,,\ \ 5\,,\ \ 7\,,\ \ 9\,,\ \ 11\,,\ \ \ldots}$$ can be defined in either of the following ways:

Concept Practice