# How can I systematically find a solution to this problem?

While doing some self-study, a friend posed this problem to me:

Let $a$ be a sequence, defined as following:

$$a_0 = 0,\quad a_1= 1, \qquad a_{n+2}=\frac{a_n+a_{n+1}}2$$

Figure out, whether $a$ converges, and if yes to which value. Find a closed form for $a_n$. If you want to, you may also have a look at the common case with $a_0= \alpha$ and $a_1 = \beta$.

It's easy to see, that this converges to $\frac2 3$, and the other parts are also easy to solve with quessing a result and afterwards proving it correct, but I dislike this approach, as it is not productive if the solution isn't obvious.

Is there a systematically approach for such problems? I would be really happy if somebody can explain me, how to systematically solve problems like this.

-
See for example en.wikipedia.org/wiki/Recurrence_relation . This is a linear homogeneous recurrence with constant coefficients and there indeed is a systematical way to solve such relations. –  J. J. Feb 12 '11 at 16:27

## 4 Answers

If the recurrence relation is linear, homogeneous and has constant coefficients, here is a systematic way to solve it. Similar method will work if you have linear, inhomogeneous equation with constant coefficients. (For instance if the inhomogeneity is a constant, the inhomogeneity can be removed if possible by defining $b_n = a_n + c$ and figuring out $c$ such that the equation in $b_n$ is homogeneous. If it is not possible, which happens when the sum of the coefficients of $a_n$ add up to zero, then there is a linear growth term added to $a_n$)

First obtain the characteristic equation. To do this, assume $a_n = m^n$.

Plug it in to get a quadratic in $m$ in this case. Solve for $m$. (If you have $a_n$ depending on $a_{n-1},a_{n-2},\ldots,a_{n-p}$, you will get a $p^{th}$ order polynomial.)

Get the two roots say $m_1, m_2$. (In general, the $p$ roots).

Now the general solution is given by the linear combination of the roots namely $a_n = c_1 m_1^n + c_2 m_2^n$. (In general, $a_n = \displaystyle \sum_{k=1}^p c_k m_k^n$)

Solve for $c_1$ and $c_2$ (In general, $c_1,c_2,\ldots,c_p$) using the initial conditions

For your recurrence, the corresponding equation becomes, $2m^2-m-1 = 0 \Rightarrow (2m+1)(m-1) = 0 \Rightarrow m = -\frac{1}{2},1$

Hence, $a_n = c (-\frac{1}{2})^n + d$

If $a_0 =0, a_1 =1$, we get $c + d = 0$ and $d - \frac{c}{2} = 1$

$d = \frac{2}{3}$ and $c = -\frac{2}{3}$

Hence, $a_n = \frac{2}{3} - \frac{2}{3} (-\frac{1}{2})^{n}$

Hence, $\displaystyle \lim_{n \rightarrow \infty} a_n = \frac{2}{3}$

If $a_0 =\alpha, a_1 =\beta$, we get $c + d = \alpha$ and $d - \frac{c}{2} = \beta$

$c = \frac{2}{3}(\alpha-\beta)$, $d = \frac{\alpha + 2 \beta}{3}$

Hence, $a_n = \frac{\alpha + 2 \beta}{3} + \frac{2}{3}(\alpha-\beta) (\frac{-1}{2})^n$

Hence, $\displaystyle \lim_{n \rightarrow \infty} a_n = \frac{\alpha + 2 \beta}{3}$

This methodology is analogous to plugging in $y=e^{mx}$ when you want to solve a linear, homogeneous ODE with constant coefficients. You get the constants for the ODE using the boundary conditions. Here you have a difference equation instead of a differential equation.

-
That's cool. Thank you very much. –  FUZxxl Feb 12 '11 at 19:52
Has this method a specific name? –  FUZxxl Feb 12 '11 at 20:06
I am not aware of any specific name for this method. You could call it by the "Method of Characteristic polynomials" or "Method of generating functions". –  user17762 Feb 12 '11 at 20:15

There are several. My favorite, and one of the most generalizable, is the use of Generating functions. These offer a systematic way of solving many recurrence relations of any order. (Yours is a 2nd order equation)

An excellent place to start learning about them is this online book.

Hope that helps.

-

Less often effective than generating functions, but in my opinion less work, is to guess that the solution to a linear homogeneous recurrence is of the form ar^n. The a is like a constant of integration Plug it in and in your case you get $ar^2=(a+ar)/2$ or $2r^2-r-1=0$. There are two roots, $r_1$ and $r_2$ so the solution is $ar_1^n+br_2^n$ Now use your initial values to find $a$ and $b$. If you have a repeated root you will have a term in $anr^n$ as well.

-
I'm a bit confused - can you explain the exact procedure on my example equation? –  FUZxxl Feb 12 '11 at 17:49
Sivaram's answer gives the details-my r is his m. –  Ross Millikan Feb 12 '11 at 20:55

I realize you're asking for a systematic answer to the problem, and others have supplied such, but there is a neat correspondence with the binary representation of 1/3.

Every iteration of the recurrence, you're dividing everything by two each time, you're going up and down each time by a negative power of 2, $1 - 1/2 + 1/4 - 1/8 + ...$ or $1/2 + 1/8 + 1/32 + ...$ essentially creating a binary encoding .1010101... which, as a geometric series comes out to $${1\over 2}\cdot{1\over 1- {1\over 4}} = {2\over 3}.$$

-
That was my approach before. With the reposity formula for geometric sequences, you can even find a closed form for even / odd $n$. But I considered it uggly, as it's unusable if you can't spot such pattern. –  FUZxxl Feb 12 '11 at 22:29