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,\ ar^{2},\ \ldots ,\ ar^{n}$

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

Arithmetic Progression

Given by: $a,\ a+d,\ a+2d,\ \ldots ,\ 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)\rightarrow 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}dxa_{n}$

Summation Formulas

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

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

The formula above can be proved by induction.

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

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