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