SECTION 2.3 Sequences, Induction and Recursion

Sequences

The term sequence informally means a set of elements written in a row. A sequence is denoted a₁, a₂, a₃, ...., a_i, where each a_i is called a term. An infinite sequence is denoted a_m, a_m+1, a_m+2, ..... A general formula for a sequence is a set of rules that show how the values of a_i  depend on i.  Consider the following example:

Given a sequence that has the following initial terms :

1/4, 1/16, 1/36, 1/64, . . . . . . .

find a general formula that represents the above sequence.

Solution: Observe the denominator of each term - each denominator is a perfect square. We can rewrite the terms as

1/(2²), 1/(4²), 1/(6²), 1/(8²). . . . . .

Now we can express each fraction as a term, where 1/(2²) = a₁, 1/(4²) = a₂, 1/(6²) = a₃, 1/(8²) = a₄, etc.  Furthermore, note that the square root of each fraction's denominator is a multiple of two. The fractions can now be rewritten as

1/(2*1)², 1/(2*2)², 1/(2*3)², 1/(2*4)². . . . . .

This sequence now has a distinct, identifiable form, where each term can be represented by the formula:

a_i = 1/(2i)²      for all integers i > 1.

The following symbols and notations are used to express different types of mathematical sequences.

	This notation represents the summation of a sequence. Each of the terms are added to represent a sum in the form ak+ ak+1 + ak+2 + ......... + an , where m < n, m is the starting point (the lower limit), and n is the last term (the upper limit).
	This is used to represent the product of the terms in a sequence, written in the form am* am+1 * am+2 *......... * an  where m and n are integers and m < n.
n!	This notation represents n factorial. It is defined to be the product of all the integers from 1 to n : n! = n * (n-1) * ........... * 3 * 2 * 1. Remark : Zero factorial is defined to be 1:    0! = 1

Properties of Summations and Products

If a_m, a_m+1, a_m+2, .... and b_m, b_m+1, b_m+2, ...... are sequences of real numbers, and r is any real number, then the following equations hold for any integers m < n:

1. a_k  + b_k  = (a_k+ b_k)

2. r  *a_k   = r  * a_k

3. (a_k) (b_k )  = (a_k * b_k ).

Try to rewrite the formula for n! in a way which allows you to factor out the initial n without specifically writing out all the terms. Click here for answer.

Mathematical Induction

To prove a statement by mathematical induction requires two steps.

1. The basis step, whereby you prove that S(m) is true for a particular integer m.
   
   
2. The inductive step, which assumes that, for every integer k > m, if S(k) is true then S(k+1) is also true (the induction). The supposition that S(k) is true is called inductive hypothesis.

Consider the following example:

We wish to show that n³ + 2n is divisible by 3.

Solution : Let P(n) stands for "n³ + 2n is divisible by 3". Using mathematical induction, we proceed as follows:

Basis step : Let n = 0. Then P(0) = 0, and 0 mod 3 = 0, so P(0) is true.

Inductive hypothesis : for all integers k > n, P(k) is true: that is, "k³ + 2k is divisible by 3" is assumed to be true.

Inductive step : If P(k) is true, then P(k+ 1) is also true.

One must now derive P(k + 1), by showing that (k + 1)³ + 2(k + 1) is divisible by 3. This is done as follows:

(k + 1)³ + 2(k + 1) = k³ + 3k² + 3k + 1 + 2k + 2

= k³ + 3k² + 5k + 3

= (k³ + 2k) + 3(k² + k + 1)

This means that (k + 1)³ + 2(k + 1) can be written as a sum of two terms. The first term is divisible by 3 if the inductive hypothesis holds, and the second term is a multiple of 3 and therefore divisible by 3 as well. Hence, we have proven that if P(n) is true, so is P(n + 1), which completes the inductive step.  Since P(0) is true, one concludes that P(n) is true for all n.

Try to follow the above steps and prove aⁱ = (aⁿ⁺¹ -1)/(a - 1), and a 1, n > 0 by using mathematical induction. Click here to see the solution.

Recursion is one of several ways to define a sequence. A sequence is said to be defined recursively if certain initial values are specified and later terms of the sequence are defined by relating them to a fixed number of earlier terms. This requires providing both an equation, which is called the recurrence relation, and a specification of the initial conditions.

1. A recurrence relation means that the later terms in the sequence depend upon the earlier terms.

2. The initial conditions are also called the base or bottom of the recursion.

Let us consider the following example. For all integers k > 2,

a_k = a_k-1 + 2 * k      recurrence relation

a₁ = 2                            initial conditions

Since a₁ = 2, a₂ and a₃ can be computed using the recurrence relation..

a₂ = a₁ + 2 * 2     by substituting k = 2 into recurrence relation

     = 2 + 4 = 6      since a₁ = 2 by initial conditions

 a₂ = 6

a₃ = a₂ + 2 * 3     by substituting k = 3 into recurrence relation

     = 6 + 6              since a₁ = 2 and a₂ = 6

 a₃ = 12

By understanding the concepts of recurrence relations and initial conditions, we can show whether a sequence given by a general formula satisfies a certain recurrence relation. Consider the following example.

Show that the sequence 0, 1, 3, 7, ...., 2ⁿ-1, ..... for n > 0, satisfies the recurrence relation

a_k = 3a_k-1 - 2a_k-2, for all integers k > 2.

Solution:

Define the n^th term of the sequence as a_n. Then, by definition, a_n = 2ⁿ-1, for each integer n > 0.

We substitute k, k-1 and k-2 into n, we have

(i) a_k = 2^k -1

(ii) a_k-1 = 2^k-1 -1 and

(iii) a_k-2 = 2^k-2 -1 for each integer k > 2.

Then

     3a_k-1 - 2a_k-2 = 3(2^k-1 -1) - 2(2^k-2 -1)  by substituting (ii) & (iii)

= 3(2^k-1) - 3 - 2^k-1 + 2      by the rules of exponent, 2(2^k-2) = 2^k-1

= 2(2^k-1) - 1                               by basic algebra, 3(2^k-1) - 2^k-1

= 2^k -1                                           by the rules of exponents, 2(2^k-1) = 2^k

= a_k                                                  by substituting (i)

In recursively defined sequences, we need to consider two specific kinds of sequence that are used commonly in our life. The first kind is an arithmetic sequence, where each term equals the previous term plus a fixed constant. (This is used in calculating the force of gravity in physics.) The second kind is a geometric sequence, where each term equals the previous term times a fixed constant. Geometric sequences are used in calculating compound interest, certain models of population growth, radioactive decay, and the number of operations needed to execute certain computer algorithms.

   Go to next section review.
   Go to Class Agenda.