8.01a, 8.01b - Recurrence relations and induction

8.01a, 8.01b - Recurrence relations and induction

Describe a sequence either by a rule that produces the next term or by a formula that goes straight to a chosen position. In 8.01a you will move between these descriptions and handle starting indices carefully; in 8.01b you will use induction to prove formulae for sequences and their sums.

Reading a recurrence system

Start at 00, double the current number and add 11: the numbers begin 0,1,3,7,150, 1, 3, 7, 15. Can you find the term in position 2020 without writing all the intervening terms, and prove that your shortcut always works?

A rule that looks backwards is easy to run forwards. It needs a starting value, though: “double and add 11” could equally start 4,9,19,39,…4, 9, 19, 39, \ldots. The same rule does not mean the same sequence.

You already know

A sequence has an integer index, and a series adds sequence terms. Induction proves a base case and then the implication from an arbitrary case kk to case k+1k+1; checking several terms is not a proof.

Write {un}\{u_n\} for a sequence. The braces here indicate an indexed sequence, so order and repeated values matter. The sequence {1,1,2,3,…}\{1, 1, 2, 3, \ldots\} is not the same object as a set of distinct values.

Recurrence relation and recurrence system

A recurrence relation defines a term using earlier terms. A recurrence system gives the relation, the initial condition or conditions, and the allowed values of the index. For example,

u0=0,un+1=2un+1(n≥0)u_0=0,\qquad u_{n+1}=2u_n+1\quad(n\ge0)

defines the opening sequence. The relation alone does not specify its starting point. A sequence may instead start with u1u_1; a zeroth term is not compulsory.

For un+1u_{n+1}, replace every nn in the right-hand side by the current index. If that side contains nn explicitly, the value changes from step to step.

Worked example 1: generating terms from a zeroth term

Question. Given u0=2u_0=2 and un+1=3un+nu_{n+1}=3u_n+n for n≥0n\ge0, find u1,u2u_1, u_2 and u3u_3.

Plan. Use n=0,1,2n=0, 1, 2 in order, carrying each new term into the next calculation.

u1=3(2)+0=6n=0u2=3(6)+1=19n=1u3=3(19)+2=59n=2\begin{aligned} u_1&=3(2)+0=6 && n=0 \\ u_2&=3(6)+1=19 && n=1 \\ u_3&=3(19)+2=59 && n=2 \end{aligned}

Why this step? The first update uses n=0n=0, because it produces u1u_1 from u0u_0.

Answer. u1=6,u2=19,u3=59u_1=6, u_2=19, u_3=59.

Check. u3−3u2=59−57=2u_3-3u_2=59-57=2, the index used in the final update.

The next example changes only where the sequence starts. The first permitted update now uses n=1n=1, so the added term is no longer zero.

Worked example 2: generating terms from a first term

Question. Given v1=2v_1=2 and vn+1=3vn+nv_{n+1}=3v_n+n for n≥1n\ge1, find v2,v3v_2, v_3 and v4v_4.

Plan. Begin at the first allowed index, then update successively.

v2=3(2)+1=7n=1v3=3(7)+2=23n=2v4=3(23)+3=72n=3\begin{aligned} v_2&=3(2)+1=7 && n=1 \\ v_3&=3(7)+2=23 && n=2 \\ v_4&=3(23)+3=72 && n=3 \end{aligned}

Why this step? An initial value of 22 in position 11 does not play the same role as 22 in position 00 when the rule contains the index.

Answer. v2=7,v3=23,v4=72v_2=7, v_3=23, v_4=72.

Check. v4−3v3=72−69=3v_4-3v_3=72-69=3, as required.

A rule may use several preceding terms. For instance, wn+2=wn+1+wnw_{n+2}=w_{n+1}+w_n needs two consecutive initial terms to run forwards; knowing only w0w_0 leaves w1w_1 free. All particular recurrence rules and term calculations in this part are not in the formula booklet: interpret the rule supplied.

Watch out

Wrong: the first update of un+1=3un+nu_{n+1}=3u_n+n, with u0=2u_0=2, is u1=3(2)+1u_1=3(2)+1. Right: use n=0n=0 to get u1=6u_1=6. The subscript on the new term is one more than the index substituted on the right.

Keep an index column beside your working when the added term depends on nn.

Position-to-term rules

A closed form replaces the whole chain of updates by a direct calculation from the position.

Closed form

A closed form, or position-to-term formula, gives un=f(n)u_n=f(n) without requiring earlier terms. For example, un=n2+1u_n=n^2+1 for n≥0n\ge0 gives 1,2,5,10,…1, 2, 5, 10, \ldots. The rule un+1=un+2n+1u_{n+1}=u_n+2n+1 is a recurrence, not a closed form, because it still uses unu_n.

To obtain a recurrence from a closed form, compare f(n+1)f(n+1) with f(n)f(n). Differences often expose a polynomial pattern; a constant multiplier often exposes an exponential one. This is algebra, not guessing from a short list.

Worked example 3: a closed form gives a recurrence

Question. The sequence un=n2+1u_n=n^2+1 is defined for n≥0n\ge0. Find u10u_{10} and express un+1u_{n+1} in terms of unu_n and nn, including the initial condition.

Plan. Substitute 1010, then subtract the expressions at two successive indices.

u10=102+1=101direct substitutionun+1−un=(n+1)2+1−(n2+1)successive difference=2n+1expand and cancelu0=1starting value\begin{aligned} u_{10}&=10^2+1=101 && \text{direct substitution} \\ u_{n+1}-u_n&=(n+1)^2+1-(n^2+1) && \text{successive difference} \\ &=2n+1 && \text{expand and cancel} \\ u_0&=1 && \text{starting value} \end{aligned}

Why this step? Subtracting cancels the quadratic term, leaving exactly the amount added at each update.

Answer. u10=101u_{10}=101, and u0=1, un+1=un+2n+1u_0=1,\ u_{n+1}=u_n+2n+1 for n≥0n\ge0.

Check. The recurrence gives u1=1+1=2u_1=1+1=2 and u2=2+3=5u_2=2+3=5, agreeing with the closed form.

The next example changes the closed form from a polynomial to an exponential. A multiple of the old term, rather than its simple difference, now cancels the changing part.

Worked example 4: an exponential closed form

Question. The sequence vn=3×2n−1v_n=3\times2^n-1 is defined for n≥0n\ge0. Find v10v_{10} and a recurrence system for {vn}\{v_n\}.

Plan. Compare vn+1v_{n+1} with 2vn2v_n, since increasing the index multiplies 2n2^n by 22.

v10=3(1024)−1=3071substitute n=10vn+1=3×2n+1−1advance the index=2(3×2n−1)+1expose vnv0=3−1=2starting value\begin{aligned} v_{10}&=3(1024)-1=3071 && \text{substitute } n=10 \\ v_{n+1}&=3\times2^{n+1}-1 && \text{advance the index} \\ &=2(3\times2^n-1)+1 && \text{expose } v_n \\ v_0&=3-1=2 && \text{starting value} \end{aligned}

Why this step? The factor 22 matches the exponential growth; the extra +1+1 repairs the constant term.

Answer. v10=3071v_{10}=3071, and v0=2, vn+1=2vn+1v_0=2,\ v_{n+1}=2v_n+1 for n≥0n\ge0.

Check. The closed form gives 2,5,112, 5, 11; the recurrence gives 2(2)+1=52(2)+1=5, then 2(5)+1=112(5)+1=11.

Neither conversion result is in the formula booklet: derive it from the given formula. Notice that two sequences can have the same update rule but different closed forms because their initial conditions differ.

Watch out

Wrong: un+1=(n+1)2+1=n2+2u_{n+1}=(n+1)^2+1=n^2+2. Right: expand the whole square to get n2+2n+2n^2+2n+2. Increasing a subscript does not add 11 to the value.

A direct formula is useful only when it describes the entire specified sequence. The next part supplies the proof.

Proving sequence formulae

A proposed closed form must match both the initial condition and the recurrence. Induction makes those two checks prove every term.

Return to the opening sequence. Adding 11 to each displayed term gives 1,2,4,8,161, 2, 4, 8, 16, suggesting un+1=2nu_n+1=2^n. That pattern suggests the formula; the recurrence proves it.

Continue this lesson.

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

Create free account