Chapter Four

Sequences and Mathematical Induction

Section 4.1

Sequences

The following solutions make use of information found in pages 180-190 of the textbook.

Exercise 4.1.1:  Definitions

Fill in the blanks to complete the following sentences.

1. In a sequence, each individual element is called a term.
2. An explicit or  general formula for a sequence is a rule that shows how the values of each term a_k depend on k.
3. In expanded form,

   n	ak	=	am + am+1 + am+2 + am+3 + ... + an.
   S
   k = m

4. For each positive integer n, n!, read as n factorial, is defined to be the product of all the integers from 1 to n:
   n! = n · (n - 1) · ... · 3 · 2 · 1.
5. Zero factorial is defined to be 1, that is 0! = 1.

Exercise 4.1.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Compute the first four terms of the sequence

ai	=	(-1)i+1	n	for all integers i 0.
			i + 3

Hint
Full solution

2. Find an explicit formula for a sequence that has the following
initial terms:  -1, 4, -27, 256, -3125, ....

Hint
Full solution

3. Write the following summation in expanded form by writing out the
first 5 terms and the final term.

Hint
Full solution

4. Express the following using summation notation.

Hint
Full solution

5.

Hint
Full solution

6.

Hint
Full solution

7. Simplify the following:

Hint
Full solution

Section 4.2

Mathematical Induction I

The following solutions make use of information found on pages 194--204 of the textbook.

Exercise 4.2.1:  Definitions

Fill in the blanks to complete the following sentences.

1. Principle of Mathematical Induction:
   Let P(n) be a statement that is defined for integers n, and let a be a fixed integer. Suppose that:
   1. P(a) is true.
   2. For all integers ka, if P(k) is true, then P(k+1) is true.
   Then the statement P(n) is true for all integers na.
2. A proof of a statement P(n) by mathematical induction involves two steps.
   In the basis step, you prove that P(a) is true for a particular integer a.
   In the inductive step, you  suppose that P(k) is true and then you  show that P(k+1) is true.
3. The supposition that P(k) is true is called the inductive hypothesis.

Exercise 4.2.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Using the Principle of Mathematical Induction to help you write out a combination of 2 and 5 cent coins which would be equivalent to
a) 13 cents    b) 16 cents    c) 21 cents.

Full solution

2. Follow the format of the proof given in your workbook to prove the following claims.

a) For all integers n1,	n	(2i - 1)	=	n2.
	S
	i = 1

Hint
Full solution

b) For all integers n1,	n	1     j (j + 1)	=	n   . n + 1
	S
	j = 1

Hint
Full solution

c) For all integers n1,	n	2j-1	=	2n - 1.
	S
	j = 1

Hint
Full solution

Section 4.3

Mathematical Induction II

The following solutions make use of information found on pages 205-210 of the textbook.

Exercise 4.3.1:   Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

Use mathematical induction to prove the following statements. To aid the clarity of your proofs, you should follow the format introduced in the previous section. Always state P(a) (where a is the value for your basis step), P(k) and P(k+1) before you begin the body of your proof

1. Prove that for all integers n1, the product  n(n+1)(n+2)  is divisible by three.

Hint
Full solution

2. Prove that  n! > 2ⁿ for all integers n4.

Notice that here we are only interested in n 4 so your basis step should be P(4).

Hint
Full solution

3. A sequence  b₀, b₁, b₂,... is defined by letting b₀ = 7 and  b_i = b_i-1 - 4  for all integers   i1. Prove that  b_n = 7 - 4n  is a general formula for this sequence for all integers  n0.

Hint
Full solution

Section 4.4

Strong Mathematical Induction and the Well-Ordering Principle

The following solutions make use of information found on pages 212-219 of the textbook.

Exercise 4.4.1:  Definitions

Fill in the blanks to complete the following sentences.

1. Principle of Strong Mathematical Induction:
   Let P(n) be a statement that is defined for integers n, and let r be a fixed integer with 1r. Suppose the following two statements are true:
   1. P(1), P(2), P(3), ..., P(r) are all true.
   2. For any integer k r, if P(i) is true for all integers i with 1 < i < k, then P(k) is true.
   Then the statement P(n) is true for all integers n 1.
2. State the Well-Ordering Principle for the Integers
   Let S be a set containing one or more integers all of which are greater than some fixed integer. Then S has a least element.
   

Exercise 4.4.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. For each of the following sets, if the set has a least element, state what that least element is. If there is no least element, explain why the well-ordering principle for the integers does not apply.

a) The set of all nonnegative even integers.

b) The set of all negative integers of the form  46 - 7k, where  k Z.

Hint
Full solution

2. Suppose that  b₁, b₂, b₃, ...  is a sequence defined as follows:  b₁ = 2,   b₂ = 4,  b_r = 5b_r-1 - 6b_r-2  for all integers  r3.
Prove (using Strong Mathematical Induction) that b_n = 2ⁿ for all integers n1.

Hint
Full solution

3. Read and understand the proof of Divisibility of a Prime given below. This proof (by contradiction) uses the Well-Ordering Principle for the Integers.  The contradiction is written in red.

Every positive integer greater than one has a prime divisor.

Proof Assume that there is a positive integer greater than one which does not have a prime divisor. Then since the set of positive integers greater than one with no prime divisors is non-empty, the Well-Ordering Principle says that there is a least positive integer n, greater than one, with no prime divisors. Since n has no prime divisors and n divides n, n is not prime. Hence we can write n = a·b with  1 < a < n and 1 < b< n. Since a < n,  a must have a prime divisor, say p (recall that n was the least positive integer with no divisors). But p | a and a | n so p | n, contradicting the fact that n has no prime divisors.

Back to workbook solution page