Skip to content

Limits of recursive sequences ​

General steps ​

In order to prove that a recursive sequence (an) converges to a limit A, we need to show that:

  1. (an) is monotonically increasing or decreasing.
  2. (an) is bounded.
  3. Find the limit A.

Example 1 ​

Determine the limit of the recursive sequence

a1=0an+1=2+an

Is a2>a1?

a2=2+a1=2

a2>a1✓

Is (an) monotonically increasing? Proving by induction:

  1. n=1⟹a2>a1
  2. Assume that an+1>an for some n∈N+
  3. Need to prove that an+2>an+1
2+an+1>2+an⇔2+an+1>2+an⇔⇔an+1>an

Which is what we assumed.

Therefore (an) is monotonically increasing. ✓

Is (an) bounded?

∀n∈N an≥0=a1min(an)=0

Therefore (an) is bounded from below.

Is (an) bounded from above?

Possible limits?

Assume that (an) converges to some limit A.

limn→∞an=Alimn→∞an+1=Alimn→∞2+an=Alimn→∞2+limn→∞an=A2+A=A⇔A2−A−2=0A=2∨A=−1

But A=−1 is not possible because an≥0 and sequence is monotonically increasing.

Prove that A=2 is the upper bound by induction:

  1. n=1⟹a1=0<2
  2. Assume that an<2 for some n∈N+
  3. Need to prove that for (n+1)⟹an+1<2⇔2+an<2
2+an<4an<2

Which is what we assumed.

Therefore (an) is bounded from above. ✓

So (an) is monotonically increasing ✓ and bounded ✓, therefore (an) is convergent.

limn→∞an=2

Example 2 ​

Determine the limit of the recursive sequence

a1=14an+1=1−1−an

Is a2>a1?

a2=1−1−a1=1−1−14=1−32=2−3214<2−32⇔1<4−23⇔23<3⇔12<9

Therefore a2<a1.

Is (an) monotonically decreasing? Proving by induction:

  1. n=1⟹a1>a2
  2. Assume that an>an+1 for some n∈N+
  3. Need to prove that an+1>an+2
1−1−an>1−1−an+1⇔1−an<1−an+1⇔⇔1−an<1−an+1⇔an>an+1

Which is what we assumed.

Therefore (an) is monotonically decreasing. ✓

Is (an) bounded?

∀n∈Nan≤14max(an)=14

Therefore (an) is bounded from above.

Is (an) bounded from below?

Possible limits?

Assume that (an) converges to some limit A.

limn→∞an=Alimn→∞an+1=Alimn→∞1−1−an=A1−1−A=A⇔1−A=1−A⇔(1−A)2−(1−A)=0(1−A)(1−A−1)=0⇔A=1∨A=0

But A=1 is not possible because an≤14 and sequence is monotonically decreasing.

Prove that A=0 is the lower bound by induction:

  1. n=1⟹a1=14>0
  2. Assume that an>0 for some n∈N+
  3. Need to prove that for (n+1)⟹an+1>0⇔1−1−an>0
1>1−an⇔1>1−an⇔an>0

Which is what we assumed.

Therefore (an) is bounded from below. ✓

So (an) is monotonically decreasing ✓ and bounded ✓, therefore (an) is convergent.

limn→∞an=0