Introduction to Recursion and Sequences

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:
$u(1) = 1^2 = 1$
$u(2) = 2^2 = 4$
$u(3) = 3^2 = 9$
$u(4) = 4^2 = 16$
$u(5) = 5^2 = 25$

The

$\,27^{\text{th}}\,$ term of the sequence defined by $\,u_n = n + 3\,$ is:
$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

$\,u_1 = 2\,$;

$\,u_n = u_{n-1} + 3\,$ for $\,n\ge 2\,$

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: $\,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

$w_1 = 1\,$, $\,w_2 = 1\,$;

$w_n = w_{n-1} + w_{n-2}\,$ for $\,n\ge 3$

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 $\,3\,$, $\,5\,$, $\,7\,$, $\,9\,$, $\,11\,$, $\,\ldots$
can be defined in either of the following ways:

as a recursive sequence:
$u_1 = 3\,$;
$u_n = u_{n-1} + 2\,$ for $\,n\ge 2$
Why is this description recursive?
Because to find a member in the list, you need to know a prior member in the list.
In particular, to find $\,u_n\,$, you need to know $\,u_{n-1}\,$.
That is, to find a member in the list, you need to know the immediately preceding member in the list.
as a nonrecursive sequence:
$u_n = 2n + 1\,$ for $\,n\ge 1\,$
Note that nonrecursive means not recursive.
Why is this description nonrecursive?
Because to find a member of the list, you don't need to know any earlier members of the list.
For example, you could find the tenth member in the list without knowing any of the prior members:
$\,u_{10} = 2(10) + 1 = 21\,$

Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Arithmetic and Geometric Sequences

(MAX is 14; there are 14 different problem types.)