# Another recurrence sequence problem

I'm working on the following problem:

Let be the sequence $x_{n}$, $n \geq0$, $x_{0}=1$,$x_{1}=0$ where $x_{n+2}-2x_{n+1}+2x_{n}=0.$

I need to find out the $x_{n}$, and i'm looking for an easy approaching way to solve it. (if possible)

-

There’s a perfectly good theory of homogeneous second-order linear recurrences with constant coefficients that can be found in most introductory discrete math texts, but for this recurrence a little experimentation suffices. From these data

$$\begin{array}{rr|rrrr|rrrr|rrrr|rrrr} n:&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ x_n:&1&0&-2&-4&-4&0&8&16&16&0&-32&-64&-64&0 \end{array}$$

it’s easy to conjecture that

\left\{\begin{align*} x_{4k+1}&=0\\ x_{4k+2}&=(-1)^{k+1}2^{2k+1}\\ x_{4k+3}&=(-1)^{k+1}2^{2k+2}\\ x_{4k+4}&=(-1)^{k+1}2^{2k+2}\;. \end{align*}\right.

This is easily proved by induction.

-
very nice and easy way. – user 1618033 Jun 1 '12 at 11:25
did you go this way because you noticed that the roots of the characteristic polynomial are nonreal? Usually, if the roots are nonreal then the values of the sequence repet? – user 1618033 Jun 1 '12 at 11:34
@Chris: It was a combination of things. I’ve a tendency to generate a little data whenever I’ve a recurrence to deal with, the recurrence, written as $x_n=2(x_{n-1}-x_{n-2})$ is especially easy to work with, and yes, I did notice the non-real roots. I’ve never thought about the general effect of non-real roots; I should probably do so. – Brian M. Scott Jun 1 '12 at 11:37
OK. At first i thought you resorted to this solution noticing that the characteristic polynomial has non-real roots, and hence the fact the values of the sequence repet. Anyway, it's a good idea to generate a little data when having to deal with recurrence. – user 1618033 Jun 1 '12 at 11:43

This is a second order homogeneous linear recurrence with constant coefficients. These have a very well developed theory that is worth learning. For example, with this problem we would see that the characteristic polynomial of this recurrence is $\lambda^2 - 2\lambda + 2 =0$ and the solution to this recurrence is of the form $x_n = a \lambda_1^n + b \lambda_2^n$ where $a,b$ are determined by the initial conditions.

If you don't know it, we can do things a bit more from scratch. For example we can use the method of generating functions: Let $$A(z) = \sum_{n=0}^{\infty} x_n z^n.$$ We can use the given recurrence to form an equation relating $A$ to itself:

$$A(z) = 1+ \sum_{n=2}^{\infty} (2x_{n-1} - 2x_{n-2}) z^n= 1 + 2z\sum_{n=2}^{\infty}x_{n-1}z^{n-1} - 2z^2 \sum_{n=2}^{\infty}x_{n-2}z^{n-2}$$

$$= 1+ 2z(A(z)-1) - 2z^2A(z).$$

Thus we have $A(z)=\displaystyle \frac{ 1 - 2z}{1-2z+2z^2}.$ You can now perform partial fractions and expand the resulting terms as geometric series to return the coefficients, which were $x_n.$

-
For this particular problem, the roots are nonreal, so if you want to express the answer wholly in terms of real numbers, you have some extra steps to do. But it is routine and can be found in many discrete math textbooks. – Gerry Myerson Jun 1 '12 at 11:21
@Ragib Zaman: does it work easy with nonreal roots? – user 1618033 Jun 1 '12 at 11:26
@Chris It works perfectly well, some may just find it aesthetically unappealing to invoke the use of complex numbers. – Ragib Zaman Jun 1 '12 at 11:29
@Ragib Zaman: OK. Thanks. – user 1618033 Jun 1 '12 at 11:30

We do the calculation using the standard characteristic equation method, in order to show how to deal with non-real roots. Our characteristic equation is $x^2-2x+2=0$, which has the roots $x=1\pm i$.

So we expect the solutions of the recurrence to have shape $$x_n=A(1+i)^n+B(1-i)^n.$$ Note that $A$ and $B$ need not be real. The initial condition $x_0=1$ yields $A+B=1$. The condition $x_1=0$ yields $A(1+i)+B(1-i)=0$. We have two linear equations in two unknowns. It turns out that $A=\frac{1}{2}(1+i)$ and $B=\frac{1}{2}(1-i)$, and therefore $$x_n=\frac{1}{2}\left((1+i)^{n+1} + (1-i)^{n+1}\right).\tag{1}$$ Since Expression $(1)$ may not be pleasing to everyone, we will massage it a bit.

Note that $$1+i=\sqrt{2}\left(\frac{1}{\sqrt{2}}+i\frac{1}{\sqrt{2}}\right)=\sqrt{2}\left(\cos\theta+i\sin \theta\right),$$ where $\theta=\pi/4$. (The above is the standard polar expression for $1+i$.) By De Moivre's Theorem, we have $$(1+i)^{n+1}=2^{(n+1)/2}\left(\cos (n+1)\theta +i\sin(n+1)\theta\right).$$ For $(1-i)^{n+1}$, take the complex conjugate. Putting things together, we find that $$x_n=2^{(n+1)/2} \cos\left(\frac{(n+1)\pi}{4}\right).\tag{2}$$ The values of cosine at integer multiples of $\pi/4$ cycle with period $4$, and have simple values, so Equation $(2)$ can be replaced by a more useful "cases" expression.

Remark: A similar procedure can be used more generally. Non-real solutions of the characteristic equation typically give cosine and sine terms. But cosine and sine terms need not give the kind of partial periodicity we got here. In general, if $a+bi$ is a root of the characteristic equation, then the argument (angle) of $a+bi$ will not be a rational multiple of $\pi$. So although the trigonometric functions will show periodic behaviour, their period wll not have a simple connection with $n$.

-
do you have in mind a counterexample of homogeneous second-order linear recurrence where non-real roots don't give partial periodicity? If there is no such a rule then i ask myself when partial periodicity happens. Your comment is very welcome to clarify things. – user 1618033 Jun 1 '12 at 15:11
the idea with the partial periodicity is that one may solve such a problem by only giving some values to recurrence and get the final answer as Brian did.It's an amazing shortcut. – user 1618033 Jun 1 '12 at 15:19
@Chris: $2x_{n+2}-x_{n+1}+x_n=0$. This is because $\arccos(1/4)$ is not a rational multiple of $\pi$. Actually, the sme thing will happen with most quadratic characteristic equations with integer coefficients, since the cosine of a rational multiple of $\pi$ is hardly ever of the shape $\sqrt{a}/b$, with $a$ and $b$ integers. – André Nicolas Jun 1 '12 at 15:42
OK. Thanks for explanations. – user 1618033 Jun 1 '12 at 15:46