1.7 - Proof by induction for sequences

1.7 - Proof by induction for sequences

A recurrence tells you how to produce the next term; a closed formula tells you a term directly from its index. In this part of 1.7, you will prove that these two descriptions agree, take care over the first index, and use the same logic to establish patterns in repeated derivatives.

Starting a recurrence proof

The sequence 0,1,3,7,15,…0,1,3,7,15,\ldots comes from doubling the previous term and adding 11. Can you find a term far along the sequence without calculating every preceding term? A formula will do that, but its index must agree with the given starting term.

A recurrence relation defines a term using one or more earlier terms. Here we use first-order recurrences, which give the next term from the current one. The initial value is part of the definition: the same recurrence with another initial value generally gives a different sequence.

Closed form

A closed form gives unu_n directly in terms of nn, without first calculating un−1u_{n-1}. To prove a proposed closed form by induction, verify its initial value and use the recurrence to establish the next case.

For example, the recurrence un+1=2unu_{n+1}=2u_n with u1=3u_1=3 gives 3,6,12,…3,6,12,\ldots. The first term involves no doubling yet, so its power of 22 is zero.

Worked example 1: a sequence indexed from one

Question. A sequence is defined by u1=3u_1=3 and un+1=2unu_{n+1}=2u_n for positive integers nn. Prove that un=3⋅2n−1u_n=3\cdot2^{n-1}.

Plan. Check the formula at n=1n=1, then substitute the hypothesis into the given recurrence.

At n=1n=1, the formula gives 3⋅20=3=u13\cdot2^0=3=u_1. Assume that

uk=3⋅2k−1u_k=3\cdot2^{k-1}

for an arbitrary positive integer kk. By the recurrence,

uk+1=2uk=2(3⋅2k−1)use the hypothesis=3⋅2k=3⋅2(k+1)−1.\begin{aligned} u_{k+1}&=2u_k\\ &=2\bigl(3\cdot2^{k-1}\bigr) &&\text{use the hypothesis}\\ &=3\cdot2^k\\ &=3\cdot2^{(k+1)-1}. \end{aligned}

This is the proposed expression at the next index.

Answer. un=3⋅2n−1u_n=3\cdot2^{n-1} for every positive integer nn, by induction.

Check. Four successive doublings from u1u_1 give u5=3×16=48u_5=3\times16=48, agreeing with 3⋅25−13\cdot2^{5-1}.

Change only the label of the starting term from u1u_1 to v0v_0, retaining its value and the doubling rule. The same list of values now has different indices.

Worked example 2: a sequence indexed from zero

Question. Let v0=3v_0=3 and vn+1=2vnv_{n+1}=2v_n for integers n≥0n\geq0. Prove that vn=3⋅2nv_n=3\cdot2^n.

Plan. Start the base case at 00; the recurrence then advances to every nonnegative index.

At n=0n=0, 3⋅20=3=v03\cdot2^0=3=v_0. Assume vk=3⋅2kv_k=3\cdot2^k for an arbitrary integer k≥0k\geq0. Therefore

vk+1=2vkgiven recurrence=2(3⋅2k)hypothesis=3⋅2k+1.\begin{aligned} v_{k+1}&=2v_k &&\text{given recurrence}\\ &=2\bigl(3\cdot2^k\bigr) &&\text{hypothesis}\\ &=3\cdot2^{k+1}. \end{aligned}

The result at k+1k+1 follows from the one at kk.

Answer. vn=3⋅2nv_n=3\cdot2^n for every integer n≥0n\geq0, by induction.

Check. The value 4848 now occurs at v4v_4, since four doublings follow v0v_0. This agrees with 3⋅243\cdot2^4 and explains the one-place difference from u5u_5.

The recurrence is the bridge between cases. Substituting k+1k+1 into the proposed formula only states the target; it does not prove that the sequence reaches it.

Watch out

For u1=3u_1=3 with doubling, un=3⋅2nu_n=3\cdot2^n fails immediately at n=1n=1. Check the initial index before attempting the algebraic step.

Start at the specified index in the next proof.

Establishing a closed form

An added term in a recurrence must be carried through the substitution; it can be the very term that makes the proposed formula simplify.

Return to 0,1,3,7,15,…0,1,3,7,15,\ldots, indexed from u0=0u_0=0. Each term is one less than a power of 22. This suggests un=2n−1u_n=2^n-1. To establish the conjecture, start from the recurrence defining the sequence, not from the formula you hope is true.

Problem-solving

Write the next-case target separately. Then substitute the whole hypothesised expression into the recurrence, using brackets so that multipliers reach every term.

The first example has a constant added term. In the second, only that added term changes: it becomes an exponential depending on the index.

Worked example 3: a constant added at each step

Question. Let u0=0u_0=0 and un+1=2un+1u_{n+1}=2u_n+1 for integers n≥0n\geq0. Prove by induction that un=2n−1u_n=2^n-1.

Plan. Substitute the hypothesis into 2uk+12u_k+1, then combine the constants.

At n=0n=0, 20−1=0=u02^0-1=0=u_0. Assume uk=2k−1u_k=2^k-1 for an arbitrary integer k≥0k\geq0. Then

uk+1=2uk+1recurrence=2(2k−1)+1hypothesis=2k+1−2+1=2k+1−1.\begin{aligned} u_{k+1}&=2u_k+1 &&\text{recurrence}\\ &=2(2^k-1)+1 &&\text{hypothesis}\\ &=2^{k+1}-2+1\\ &=2^{k+1}-1. \end{aligned}

The last line is the required formula at k+1k+1.

Answer. un=2n−1u_n=2^n-1 for every integer n≥0n\geq0, by induction. In particular, the opening sequence has u100=2100−1u_{100}=2^{100}-1.

Check. Rearranging the recurrence gives un+1+1=2(un+1)u_{n+1}+1=2(u_n+1). Thus un+1u_n+1 doubles from u0+1=1u_0+1=1, independently confirming the powers of 22.

Replacing the added 11 by 3n3^n introduces a second exponential. Keep the exponent in the recurrence at kk, since the given relation links uk+1u_{k+1} to uku_k.

Worked example 4: an index-dependent added term

Question. A sequence satisfies v0=0v_0=0 and vn+1=2vn+3nv_{n+1}=2v_n+3^n for integers n≥0n\geq0. Prove that vn=3n−2nv_n=3^n-2^n.

Plan. Substitute the difference into the recurrence and collect powers with the same base.

At n=0n=0, 30−20=0=v03^0-2^0=0=v_0. Assume vk=3k−2kv_k=3^k-2^k for an arbitrary integer k≥0k\geq0. Then

vk+1=2vk+3k=2(3k−2k)+3k=3⋅3k−2⋅2k=3k+1−2k+1.\begin{aligned} v_{k+1}&=2v_k+3^k\\ &=2(3^k-2^k)+3^k\\ &=3\cdot3^k-2\cdot2^k\\ &=3^{k+1}-2^{k+1}. \end{aligned}

The multiplier 22 applies to both terms in the hypothesis. The extra 3k3^k then completes 3k+13^{k+1}.

Answer. vn=3n−2nv_n=3^n-2^n for every integer n≥0n\geq0, by induction.

Check. Direct recurrence calculations give v1=1v_1=1, v2=5v_2=5, v3=19v_3=19, v4=65v_4=65. The proposed formula at the new index 44 gives 81−16=6581-16=65.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account