﻿ Introduction to Recursion and Sequences

# 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:

• As a recursive sequence: \begin{align} &\cssId{s57}{u_1 = 3}\cr &\cssId{s58}{u_n = u_{n-1} + 2\ \ \text{for}\ \ n\ge 2} \end{align}

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 (i.e., not recursive) sequence: $$\cssId{s64}{u_n = 2n + 1\ \ \text{for}\ \ n\ge 1}$$

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: $$\cssId{s69}{u_{10} = 2(10) + 1 = 21}$$