Recursion to explicit formula

Question

I need to try to figure out the explicit formula of the sequence $x_n=\frac{(x_{n-2}+x_{n-1})}{2}$ where $x_1=0, x_2=1$. I calculated the first few terms of the sequence and graphed it, but I'm just unsure on to where to start.

Answer 1

The usual technique of assuming a solution of the form $ar^n$ works fine. If you plug it in you get $r^2=\frac 12r+\frac 12$. Solve that for the two values of $r$, then find a linear combination that matches your starting values.

Answer 2

Put $v_n := (x_n,x_{n+1})^T\in\mathbb R^2$. Then $v_1= (0,1)^T$ and $v_n = Av_{n-1}$, where $$ A = \left(\begin{matrix}0 & 1\\\frac 1 2 & \frac 1 2\end{matrix}\right). $$ Now, diagonalize $A$ so that $A = SDS^{-1}$ with a diagonal matrix $D$ having the eigenvalues of $A$ on the diagonal (these are $1$ and $-1/2$). Then with $u_n := S^{-1}v_n$ we have $u_1 = \frac 1 3(2,-1)^T$ and $u_n = Du_{n-1}$. Hence, $u_n= D^{n-1}u_1$ and thus $v_n = Su_n = SD^{n-1}u_1$ which gives you the answer if you consider only the first coordinate (which is $x_n$).

Answer 3

An alternate approach.

Writing out a few terms,

$x_1 = 0, x_2 = 1, x_3 = \frac{1}{2}, x_4 = \frac{3}{4}, x_5 = \frac{5}{8}, x_6 = \frac{11}{16}, x_7 = \frac{21}{32}, x_8 = \frac{43}{64}, x_9 = \frac{85}{128},...$

we see that the denominator is simply going up in powers of 2. In fact, if we ignore the first term, the denominator of $x_n$ is $2^{n-2}$.

The numerator is trickier. Notice that as $n \to \infty$, $x_n \to \frac{2}{3}$. In fact, the terms are oscillating between being slightly greater than $\frac{2}{3}$ and slightly less than $\frac{2}{3}$. So one way to get the numerator is to "adjust" the denominator by adding or subtracting 1 (to make it divisible by 3) and then multiplying it by $\frac{2}{3}$. Using this method, we can get the following (alternate, but nonetheless explicit) expression for the sequence:

$x_1 = 0$

$x_n = \frac{\frac{2}{3}(2^{n-2} - 1)+1}{2^{n-2}} \ \ \ \ $ for $n$ even

$x_n = \frac{\frac{2}{3}(2^{n-2} + 1)-1}{2^{n-2}} \ \ \ \ $ for $n$ odd, $n \ge 3$

Answer 4

Let me refresh your memory considering the more general case where $$x_n=a\,x_{n-1}+b\, x_{n-2}\tag 1$$ Assume that the solution is something like $x_n=C y^n$ and replace in $(1)$ to get $$C\,y^n=a\,C\,y^{n-1}+b\, C\,y^{n-2}\tag 2$$ Divide each side by $C \,y^{n-2}$ to get $$y^2=a\,y+b\tag 3$$which is a quadratic equation with roots $y_1$ and $y_2$. So the general solution is $$x_n=C_1\,y_1^n+C_2\,y_2^n\tag 4$$ Coefficients $C_1$ and $C_2$ will be fixed by the conditions. Suppose that, such as in your case, $x_1$ and $x_2$ are given; this leads to $$x_1=C_1\,y_1+C_2\,y_2\tag 5$$ $$x_2=C_1\,y_1^2+C_2\,y_2^2\tag 6$$ Two linear equations to be solved for $C_1,C_2$ since you know the values of $x_1,x_2,y_1,y_2$.

I am sure that you can take it from here.

Answer 5

Use generating functions. Define $X(z) = \sum_{n \ge 0} x_n z^n$, shift your recurrence to $x_{n + 1} = (x_{n + 1} + x_n) / 2$, multiply by $z^n$ and sum over $n \ge 0$, recognize the resulting sums, solve as partial fractions:

$\begin{align*} \frac{X(z) - x_0 - x_1 z}{z^2} &= \frac{X(z) - x_0}{2 z} + \frac{X(z)}{2} \\ X(z) &= \frac{2 (x_0 - x_1)}{3 (1 + z / 2)} + \frac{x0 + 2 x_1}{3 (1 - z)} \end{align*}$

Just two geometric sums:

$\begin{align*} X(z) &= \frac{2 (x_0 - x_1)}{3} \sum_{n \ge 0} 2^{- n} z^n + \frac{x_0 + 2 x_1}{3} \sum_{n \ge 0} (-1)^n z^n \end{align*}$

You can read off the $x_n$ from this:

$\begin{align*} x_n &= \frac{2 (x_0 - x_1)}{3} 2^{-n} + \frac{x_0 + 2 x_1}{3} (-1)^n \end{align*}$