FP2 6.3 - Proving closed forms by induction

FP2 6.3 - Proving closed forms by induction

Prove that a proposed formula gives every term of a recurrence (FP2 6.3). You will choose enough base cases, state the right inductive assumptions and use the recurrence to build the next closed form.

Use the recurrence to prove the next formula

Why does one recurrence proof need one starting case, while another needs two? The number of earlier terms used by the rule determines how much established information the induction step needs.

You already know

Induction checks a starting case, assumes a statement at an arbitrary permitted index and proves its successor. A closed form expresses unu_n directly in nn. Finding that form by an auxiliary equation is a different task from proving it by induction.

Write P(n)P(n) for the statement un=F(n)u_n=F(n). For un+1=aun+g(n)u_{n+1}=a u_n+g(n), the recurrence converts the assumed uk=F(k)u_k=F(k) into

uk+1=aF(k)+g(k)u_{k+1}=aF(k)+g(k)

Your algebra must then reach F(k+1)F(k+1).

First-order recurrence induction

For a rule beginning at index n0n_0:

  • check un0=F(n0)u_{n_0}=F(n_0);
  • assume uk=F(k)u_k=F(k) for an arbitrary integer k≥n0k\geq n_0;
  • use the recurrence to prove uk+1=F(k+1)u_{k+1}=F(k+1).

Then the formula holds for every integer n≥n0n\geq n_0.

Not in the formula booklet: learn it.

Checking many terms still does not replace that implication. Add n(n−1)⋯(n−99)n(n-1)\cdots(n-99) to any proposed formula: the values at indices 00 to 9999 stay unchanged, but the value at 100100 changes by 100!100!. A hundred successful checks can hide a false next term.

Worked example 1: build the next power

Question. A sequence satisfies un+1=2un+3u_{n+1}=2u_n+3, u0=1u_0=1. Prove by induction that

un=4⋅2n−3,n≥0u_n=4\cdot2^n-3,\qquad n\geq0

Plan. Check index 00, assume the closed form at kk, then substitute it into the next-term rule.

At n=0n=0, 4⋅20−3=1=u04\cdot2^0-3=1=u_0, so the base case holds.

Assume uk=4⋅2k−3u_k=4\cdot2^k-3 for an arbitrary integer k≥0k\geq0. Then

uk+1=2uk+3recurrence=2(4⋅2k−3)+3inductive assumption=8⋅2k−3expand and simplify=4⋅2k+1−3required next form\begin{aligned} u_{k+1}&=2u_k+3 &&\text{recurrence}\\ &=2(4\cdot2^k-3)+3 &&\text{inductive assumption}\\ &=8\cdot2^k-3 &&\text{expand and simplify}\\ &=4\cdot2^{k+1}-3 &&\text{required next form} \end{aligned}

Why this step? The recurrence gives an established equation for uk+1u_{k+1}; the formula for uk+1u_{k+1} is the result to prove, not another assumption.

Answer. If the formula is true at kk, it is true at k+1k+1. It is true at 00, so it holds for every integer n≥0n\geq0, by mathematical induction.

Check. At n=2n=2, direct iteration gives 1,5,131,5,13, and the formula gives 16−3=1316-3=13. This checks the arithmetic, not the general implication.

Change only u0u_0 from 11 to 22; the coefficient in the proposed closed form changes accordingly.

Worked example 2: the changed base case

Question. For un+1=2un+3u_{n+1}=2u_n+3, u0=2u_0=2, prove that

un=5⋅2n−3,n≥0u_n=5\cdot2^n-3,\qquad n\geq0

Plan. Check the new initial value and run the same implication with its new coefficient.

At n=0n=0, 5⋅20−3=2=u05\cdot2^0-3=2=u_0.

Assume uk=5⋅2k−3u_k=5\cdot2^k-3 for an arbitrary integer k≥0k\geq0. Then

uk+1=2uk+3recurrence=2(5⋅2k−3)+3use the assumption=10⋅2k−3simplify=5⋅2k+1−3required next form\begin{aligned} u_{k+1}&=2u_k+3 &&\text{recurrence}\\ &=2(5\cdot2^k-3)+3 &&\text{use the assumption}\\ &=10\cdot2^k-3 &&\text{simplify}\\ &=5\cdot2^{k+1}-3 &&\text{required next form} \end{aligned}

Why this step? Both the base case and the assumed statement must use the new proposed formula; the recurrence itself has not changed.

Answer. The formula is true at 00, and truth at any k≥0k\geq0 implies truth at k+1k+1. It therefore holds for all integers n≥0n\geq0, by induction.

Check. Direct iteration gives u1=7,u2=17u_1=7,u_2=17; the formula gives these same values.

A proof must follow the requested method. Solving the recurrence again may establish the formula by another argument, but it is not a proof by induction.

Watch out

“Assume uk=5⋅2k−3u_k=5\cdot2^k-3 and uk+1=5⋅2k+1−3u_{k+1}=5\cdot2^{k+1}-3” assumes the target. For this first-order proof, assume only the kk formula, then derive the k+1k+1 formula using the recurrence.

Change the initial value once more and supply the whole proof.

A second-order proof starts with two consecutive cases

For a second-order rule, the next term depends on two earlier terms. The induction step therefore assumes the proposed formula at two consecutive indices, then proves it at the following index.

Two-case recurrence induction

For a second-order recurrence starting at n0n_0, check

un0=F(n0),un0+1=F(n0+1)u_{n_0}=F(n_0),\qquad u_{n_0+1}=F(n_0+1)

Assume uk=F(k)u_k=F(k) and uk+1=F(k+1)u_{k+1}=F(k+1), for an arbitrary integer k≥n0k\geq n_0. Use the recurrence to prove uk+2=F(k+2)u_{k+2}=F(k+2).

The two initial cases start the chain; the step advances the established consecutive pair.

Not in the formula booklet: learn it.

For example, the pair 0,10,1 establishes 22; the pair 1,21,2 then establishes 33. Neither the second starting value nor the second assumption is optional.

[DIAGRAM: asset_name: Two established cases advance an induction proof; asset_slug: recurrence-two-case-induction; caption: A second-order rule uses two consecutive established cases to prove the next one.; description: The left panel contains two blue boxes P(0) and P(1) under the instruction Check both base cases. The right panel has two blue input boxes P(k) and P(k+1), whose arrows meet and lead to one sage box P(k+2). A dark-ink footer states that the implication must hold for every integer k at least0. All labels have generous clear spacing.]
A second-order rule uses two consecutive established cases to prove the next one.

The starting index is not automatically 11. Here the data begin at 00, so check 00 and 11.

Worked example 3: two power terms

Question. Let un+2=3un+1−2unu_{n+2}=3u_{n+1}-2u_n, u0=1,u1=4u_0=1,u_1=4. Prove that

un=3⋅2n−2,n≥0u_n=3\cdot2^n-2,\qquad n\geq0

Plan. Check both initial indices, assume both consecutive closed forms and combine like powers in the recurrence.

At n=0n=0, 3⋅20−2=1=u03\cdot2^0-2=1=u_0. At n=1n=1, 3⋅21−2=4=u13\cdot2^1-2=4=u_1.

Assume uk=3⋅2k−2u_k=3\cdot2^k-2 and uk+1=3⋅2k+1−2u_{k+1}=3\cdot2^{k+1}-2, for an arbitrary integer k≥0k\geq0. Then

uk+2=3uk+1−2ukrecurrence=3(3⋅2k+1−2)−2(3⋅2k−2)both assumptions=(18−6)2k−6+4write powers in 2k=12⋅2k−2collect=3⋅2k+2−2required next form\begin{aligned} u_{k+2}&=3u_{k+1}-2u_k &&\text{recurrence}\\ &=3(3\cdot2^{k+1}-2)-2(3\cdot2^k-2) &&\text{both assumptions}\\ &=(18-6)2^k-6+4 &&\text{write powers in }2^k\\ &=12\cdot2^k-2 &&\text{collect}\\ &=3\cdot2^{k+2}-2 &&\text{required next form} \end{aligned}

Why this step? A common power lets you combine coefficients explicitly; merely writing the target after substitution leaves the important algebra unshown.

Answer. Truth at k,k+1k,k+1 implies truth at k+2k+2. Both 0,10,1 have been checked, so the formula holds for every integer n≥0n\geq0, by induction.

Check. The recurrence gives u2=10u_2=10, agreeing with 3(4)−23(4)-2.

Change only u1u_1 from 44 to 55; the resulting closed form changes, but the proof still needs two starting cases.

Continue this lesson.

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

Create free account