### Unit 4: Mathematical Induction and Introduction to Sequences

In the field of computer science, we are often required to prove the correctness of an algorithm. Mathematics has a variety of methods in order to do just that, one of which is known as mathematical induction. In this unit, we will learn to use induction in order to determine whether mathematical sequences are valid or invalid. This lesson is extremely important, because mathematical sequences are the basis for the study of repeated processes.

This unit will present induction first in an abstract form and then through specialized proofs of sequences. We will examine mechanisms for finding the general formula for a sequence and apply mathematical induction to prove a given formula's validity.

**Completing this unit should take you approximately 23 hours.**

Upon successful completion of this unit, you will be able to:

- analyze sequences and series, which use summation, product, and factorial operations;
- write the terms of a sequence as a generalized formula;
- use mathematical induction to prove the validity of a series; and
- apply sequences, series, and induction to repeated processes.

### 4.1: Sequences

Read Section 2, "Sequences" on pages IS-12 - IS-19. In addition, read the examples mentioned below. This reading also applies to subunits 4.1.2 and 4.1.3.

See the definition of alternating sequence, immediately before example 14. Please pay particular attention to examples 7, 14 (optional), and 17 for information specific to the topics in subunits 4.1.2 and 4.1.3. Given a sequence, f(k), f(k + 1), f(k + 2), f(k + 3), ..., where k is a fixed integer, we may be able to determine a general expression for each term of this sequence. The general expression will have the form f(n), where n is a variable that takes on values from the set {n, n > k}. If we can determine the form for f, we write f(n)n >= k. See the exercises for section 2 for examples.

If one takes the first term of a sequence, then the sum of the first two terms, then the sum of the first three terms, and so on, the result is a new sequence, called a series. Alternating series are defined on page IS-24 of the Bender and Williamson reading above. An alternating sequence is defined just like an alternating series; namely, the signs of the adjacent terms of the sequence alternate in their signs.

The problem of finding an explicit formula for a sequence or series is, in general, a hard problem. In some cases, there might not even exist such a formula.

Finding an explicit formula pertains to three situations:

- Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on the n-1 term.
- Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on n.
- Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on one or more of the preceding terms.

If the sequence has certain properties - such as the ability of each term to be calculated from the preceding term - as in an arithmetic sequence (where a fixed number is added to the n-1 term to obtain the nth term), or a geometric sequence (where a fixed number is used to multiply the n-1 term, to obtain the nth term), then one could use that information to deduce a formula for each term. Thus, one makes assumptions about the relationship of the n-1 term and the nth term. Or, if one is given a formula for each term that depends on that term, one could deduce a formula for the nth term.

An example for the third situation above is that of the Fibonacci series - f(n) = n + (n-1) and f(0) = 0, f(1) = 1.

- Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on the n-1 term.

### 4.2: Summation

Read this lecture. Take your time to understand the transition from one step to the next in the proofs. This can be time consuming, but it is rewarding. Don't let the topic of the examples - annuities, for example - distract you. The domains (e.g. annuities, Taylor series, etc.) are important, but so is the method they illustrate. The method is more general than the specific domain of the example.

The reading mentions induction as a way of proving some of the expressions and then continues to give insight into the source of the expression. We will cover induction in Subunit 4.5 of this course.

Read Section 3 on pages 20 - 30.

For sequences, given a summation ∑n > = k (f(n), we can expand it to the series, f(k), f(k) + f(k + 1), f(k) + f(k + 1) + f(k + 2), .... Given the series, f(k), f(k) + f(k + 1), f(k) + f(k + 1) + f(k + 2), f(k) + f(k + 1) + f(k + 2) + f(k + 3), ..., we can write it as ∑n >= k f(n).

Read this brief note on summation.

### 4.3: Products

### 4.3.1: Product Notation

Read Section 1 on pages 1 - 11. ∏ is the symbol for product. If p1 , p2, ... , pk ... is a sequence, the series p1 , p1 p2 , p1 p2 p3 , p1 p2 , ... , pk is written ∏ p1 p2 ... pk. If you look over the exercises for section 1, you will see that this reading applies to ∏ examples as well as ∑ examples. This reading also applies to topics in Subunit 4.3.2.

### 4.3.2: Computing Products

Study Section 3.4 "Approximating 1 + x."

Product computation is similar to the evaluation of the product of numbers in arithmetic. Product or multiplication is a binary operation that is commutative [i.e. a times b = a b = b a]; associative [i.e. (a b) c = a (b c)]; and has an identity (i.e. a times 1 = 1). In addition, there are some tricks that can be used.

Some simple properties of products are:

1. a ∏ pi = ∏ a pi, where the ∏ ranges over a set of positive integers i.

2. ∏ pi ∏ qij = ∏ pi qj, where the product symbols varies over ranges for i and j.

Read Theorem 11 and example 17 on pages IS-27 through IS-30. In doing calculation involving series, we work with sums (since a series is the sum of the succeeding terms of a sequence). In working these calculations, we also encounter the product of terms, for example when determining whether a series is bounded.

### 4.4: Factorial Notation

Read Section 2 "The Factorial Function." The reading also applies to the Subunit 4.4.1 and Subunit 4.4.2. In reading for Subunit 4.4.2, below, see the binomial theorem and its generalization to the multinomial theorem.

Note the first ten factorials: 10! 9! 8! 7! 6! 5! 4! 3! 2! 1! = 10

_{1}x 9_{2}x 8_{3}x 7_{4}x 6_{5}x 5_{6}x 4_{7}x 3_{8}x 2_{9}x 1_{10}.In "Counting II", read Section 1.3, "Permutations." In "Counting III", read Section 1.3, "Combinations" and Section 2, "Binomial Theorem."

### 4.5: Mathematical Induction

You have encountered mathematical induction in some of the previous readings in this course. Read Sections 1 and 2 on pages 1 - 4. As you read about induction in the references, note that induction has a relationship to recursion. Then, read Section 3 and Section 4 on pages 5 - 7.

Read Section 2 on pages 2 - 5 and Section 4 on pages 8 - 12. These readings give helpful guidance in correct use of induction.

Study the applications of induction in Section 1 on pages IS-1 through IS-8. Then, read Section 1, example 2 on page IS-2. Finally, read Theorem 2 on pages 5 - 7, example 11 on page 22, and example 12 on page 23. Some of the examples are more difficult, but hard examples push our understanding and expand our skill. Afterwards, read example 4 on pages 3 and 4.

This reading is a good formal review. Again, the presentation relies on a lot of examples. Don't forget to look over the exercises at the end of the section. Some of these examples will be utilized in following subunits.

### 4.6: Loop Invariants

Read Section 3.2. The reading presents a proof that an initial configuration of the 9-number puzzle cannot be transformed into its inverse. The proof uses the fact that after each move the number of inversions remains even; this is an invariant. Invariants are used in proofs and in proving the correctness of programs.

Invariants are only introduced in this course; they are covered in detail in programming language courses.

### Unit 4 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment