MATH 302 Lecture 10

« previous | Monday, October 3, 2011 | next »

Chapter 5: Sequences and Summation

Sequences

function from positive integers or natural numbers to a set, but instead of using function notation ($a(n)$), we use subscript notation ($a_n$)

Examples:

• 1, 0, 2, 0, 3, 0, 4, 0, 5, …
• 5, 15, 45, 135, … (geometric: $a_n=5\cdot 3^n$)
• 3, 7, 11, 15, … (arithmetic: $a_n=3+4n$)
• 1, 1, 2, 3, 5, 8, 13, … (recurrence relation / fibonacci sequence: $f_n=f_{n-1}+f_{n-2}$)

Analyzing Sequences

we will discuss two ways:

1. closed form expression: a_n = formula or procedure
2. recurrence relation (or difference equation): a_n = f(a_n', a_n'', …)

   we'll come back to recurrence relations later

Geometric Sequences

Given by: $a,ar,a{r}^2,\dots ,a{r}^n$

• $a$ is the first term
• $r=\frac{a_{n+1}}{a_n}$

Arithmetic Progression

Given by: $a,a+d,a+2d,\dots ,a+nd$

• $a$ is the first term
• $d=a_{n+1}-a_n$

Mathematical Induction

Given a predicate $P(n)$ accepting positive integers, prove that $P(n)$ is true for all n > 0

1. Prove the basis step: Show that $P(1)$ is true.
2. Prove the induction step: Shaw that $P(k)\to P(k+1)$ for an arbitrary positive integer $k$ (Assume $P(k)$ is true, then show how $P(k+1)$ must follow.)

Application to sequences

Given a sequence $a_n=8a_{n-1}-16a_{n-2}$ and a potential candidate $a_n=4^n$, we can prove that they are equivalent using mathematical induction

$4^n=8\cdot 4^{n-1}-16\cdot 4^{n-2}$, which is true, and show that it holds for the first few terms.

Series

$a_n$ is a sequence:

$S=\sum _{i}dx{a}_n$

Summation Formulas

For a geometric sequence $a,ar,a{r}^2,a{r}^3,\dots ,a{r}^n$,

$\sum _{k=0}^{n}a{r}^k=\frac{a{r}^{n+1}-a}{r-1}$

The formula above can be proved by induction.

For aritmetic equences $a,a+d,a+2d,a+3d,\dots ,a+nd$,

$\sum _{k=0}^{n}a+kd=\frac{a+a_n}{2}n$