Home » Blog » Compute the limit of the recursive sequence an+1 = (an + an-1) / 2

Compute the limit of the recursive sequence an+1 = (an + an-1) / 2

by RoRi

Let \{ a_n \} be the recursively defined sequence

    \[ a_{n+1} = \frac{a_n + a_{n-1}}{2} \qquad \text{for } n \geq 2, \]

where the first two terms are given a_1 and a_2.

  1. Assume that this sequence \{ a_n \} converges and compute its limit in terms of the initial terms a_1 and a_2.
  2. Prove that the sequences converges for every choice of a_1 and a_2. Assume a_1 < a_2.
  1. Assume the limit exists, say

        \[ \lim_{n \to \infty} a_n = L. \]

    Then, we have

        \[ a_n + 2a_{n+1} = a_n + 2 \cdot \left( \frac{a_n + a_{n-1}}{2} \right) = a_{n-1} + 2a_n. \]

    Hence, the value a_n + 2a_{n+1} does not depend on n, and we have

        \[ a_n + 2a_{n+1} = a_1 + 2a_2. \]

    Now, taking the limit

        \begin{align*} && \lim_{n \to \infty} \left( a_n + 2a_{n+1} \right) &= \lim_{n \to \infty} (a_1 + 2a_2) \\[9pt] \implies && 3L &= a_1 + 2a_2 \\[9pt] \implies && L &= \frac{1}{3} a_1 + \frac{2}{3} a_2 \\[9pt] \implies && \lim_{n \to \infty} a_n &= \frac{1}{3} a_1 + \frac{2}{3} a_2. \end{align*}

  2. Proof. Assume a_1 < a_2 and let d = a_2 - a_1 > 0. Now, we claim for n \geq 2 that

        \[ a_{n+1} = a_n + (-1)^{n-1} \cdot \frac{a_2-a_1}{2^{n-1}}. \]

    We prove this claim by induction. For the case n = 2 we have

        \[ a_3 = \frac{a_2 + a_1}{2} = a_2 + \frac{a_1 - a_2}{2} = a_2 + (-1) \cdot \frac{a_2 - a_1}{2} = a_n + (-1)^{n-1} \cdot \frac{a_2 - a_1}{2^{n-1}}. \]

    So the statement is indeed true for the case n = 3. Now, assume the statement is true for some integer k \geq 2. Then we have

        \begin{align*} a_{k+2} &= \frac{a_{k+1} + a_k}{2} \\[9pt] &= \frac{ a_k + (-1)^{k-1} \cdot \frac{a_2-a_1}{2^{k-1}} + a_k}{2} &(\text{Ind. Hyp.}) \\[9pt] &= \frac{2^{k-1}a_k +(-1)^{k-1} (a_2 - a_1) + 2^{k-1} a_k}{2^k} \\[9pt] &= \frac{2^k a_k + (-1)^{k-1} (a_2 - a_1)}{2^k} \\[9pt] &= a_k + (-1)^{k-1} \cdot \frac{a_2-a_1}{2^k} \\[9pt] &= a_{k+1} - (-1)^{k-1} \frac{a_2-a_1}{2^{k-1}} + (-1)^{k-1} \cdot \frac{a_2-a_1}{2^k} &(\text{IH for term } a_k)\\[9pt] &= a_{k+1} - 2 \cdot (-1)^{k-1} \frac{a_2-a_1}{2^k} + (-1)^{k-1} \cdot \frac{a_2-a_1}{2^k} \\[9pt] &= a_{k+1} - (-1)^{k-1} \frac{a_2-a_1}{2^k} \\[9pt] &= a_{k+1} + (-1)^k \frac{a_2-a_1}{2^k}. \end{align*}

    Therefore, the proposed formula indeed holds for all integers n \geq 2. We then express this formula as a sum,

        \begin{align*} a_{n+1} &= a_n + (-1)^{n-1} \cdot \frac{a_2 - a_1}{2^{n-1}} \\[9pt] &= a_{n-1} + (-1)^{n-2} \cdot \frac{a_2 - a_1}{2^{n-2}} + (-1)^{n-1} \cdot \frac{a_2 - a_1}{2^{n-1}} \\[9pt] & \qquad \qquad \vdots \\[9pt] &= a_1 + \sum_{k=1}^n (-1)^{k-1} \cdot \frac{a_2 - a_1}{2^{n-1}}. \end{align*}

    So the terms of the sequence are the partial sums of this series. But, since a_2 - a_1 is a constant (for any given a_1 and a_2) this is a geometric series; hence, it converges. Therefore, the terms of the sequence \{ a_n \} converge to a finite limit. \qquad \blacksquare

3 comments

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):