Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
add comment

4 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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}.$$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.