Skip to main content

Subsection 8.8.8 Sequences

So far, we’ve used induction to prove claims about common sequences that we’re used to working with (for example, the positive integers or the powers of 2).

We can also use it to prove claims about arbitrary sequences, particularly ones that we define in a way that corresponds to the way in which we write inductive proofs:

  • First we specify one (or maybe two or some other small number of) elements that get the sequence going.

  • Then we specify a formula that lets us compute the remaining elements from one (or some small number) of earlier elements.

One standard notation for specifying a sequence, say s, is to write it as:

s1, s2, s3, ….

Or sometimes it’s useful to start numbering the sequence starting at 0, in which case we write it as:

s0, s1, s2, ….

Exercises Exercises

1.

1. In this problem, we’ll start by defining a sequence. Then we’ll prove something about its elements.

Define the following sequence:

a0 = 0,

For all n ≥ 0, an+1 = 3an + 1

Write out the first several elements of this sequence. What is a5?

Answer.
Correct answer is 121.

Exercises Exercises

Exercise Group.

(Continuing with the same problem) So far, it looks like the only way to determine the value of a particular element, for example a5, is first to compute the values for all the earlier elements in the sequence. But in the case of some sequences (and this is one), that’s not so. We can write a formula that gives us the value directly.

Consider the following claim: For n ≥ 0, an = \(\frac{3^{n} - 1}{2}\) .

Part 1.
Use induction to prove that this claim is true. Begin by writing out an explicit statement of P(n). Which of the following is correct:

  1. P(n) is: an = (3^n-1)/2 .

  2. P(n) is: For n  0, an = (3^n-1)/2 .

  3. P(n) is: (a_n = (3^n-1)/2)  (a_(n+1) = (3^(n+1)-1)/2).

  4. P(n) is: an+1 = 3an + 1

Answer.

Correct answer is A.

Solution.
Explanation: P(n) is: an = (3^n-1)/2 . P(n) is a claim about a particular value of n. All of the other expressions play other roles in our proof.
Part 2.

Now write out an explicit statement of the induction hypothesis. Which of the following is correct:

  1. an = (3^n-1)/2 .

  2. For n  0, an = (3^n-1)/2 .

  3. (a_n = (3^n-1)/2)  (a_(n+1) = (3^(n+1)-1)/2).

  4. an+1 = 3an + 1

Answer.
Correct answer is B
Solution.
Explanation: The induction hypothesis is that our claim is true for the value n. Then we’ll use that to show that if, that’s the case, the claim must also be true for n+1.
5.
(Continuing with the same problem) Base case: Write out a proof of the base case. When you’ve written it, click here to see ours.
Answer.

P(0) is true: a0 = 0. And (3^0-1)/2= (1-1)/2=0 .

Induction step: We must prove: (a_n = (3^n-1)/2)  (a_(n+1) = (3^(n+1)-1)/2).

Write out a proof. If you need a hint, click here. When clicked, should see:

Start by using the definition of the sequence to write an expression for an+1. Then see if you can use the inductive hypothesis to transform it into the expression that we need.

If you need another hint, click here. When clicked, should see:

Begin by writing:

an+1 = 3an + 1

Now, can you use the inductive hypothesis to rewrite the right hand side of this equation?

If you need another hint, click here. When clicked, should see:

an+1 = 3an + 1 = 3( (3^n-1)/2 )+1 Induction hypothesis

When you’ve written your proof, click here to see ours. When clicked, should see:

\begin{gather*} an+1 = 3an + 1 \\ = 3( (3^n-1)/2 )+1 Induction hypothesis\\ = (3  3^n- 3 +2)/2\\ = ( 3^(n+1)- 1)/2 \end{gather*}