Got $n$ numbers $x_1,x_2,\dots,x_n$ and a transformation which converts each element in the mean of side elements. What happen? You are given a finite sucession $x_1,x_2,\dots,x_n$ and a transformation $T$ that makes each $x_j=\dfrac{x_{j-1}+x_{j+1}}{2}$, assuming that $x_0=x_n$ and $x_{n+1}=x_1$. If I apply the transformation enough times, will this converge to somethig? Probe it.
I'm pretty sure they converge to the same value if $n$ is even, otherwise the odd elements and the even will converge to different values. But how can I probe it?
 A: Assume the $x_i\in \mathbb{R}$.
Suppose $\lambda$ is an eigenvalue of the matrix $A$ (from comments), with eigenvector $\vec{v}$.  As $A$ is symmetric, we may assume that $\vec{v}$ is a real vector.  Let $v_i$ be the entry of $\vec{v}$ of maximal modulus.  Then $$|\lambda||v_i|=|(T\vec{v})_i|\leq |v_i| $$
so $|\lambda|\leq1$.
The eigenspace for $\lambda=1$ is precisely the constant vectors ($\vec{v}$ with all $v_k$ equal).  To see this note that given an eigenvector with $v_k<v_{k-1}$ we have $v_{k+1}<v_k$.  Repeating all the way round we eventually get $v_k<v_k$, a contradiction.
Suppose $\vec{w}$ is an eigenvector for $\lambda=-1$.  Again considering the maximum modulus of a $w_i$, we have that $$\vec{w}=\left(\begin{array}{c}1\\-1\\1\\-1\\ \vdots\\1\\-1\end{array}\right)$$
up to scale, if $n$ is even, and does not exist if $n$ is odd.
Any initial values $\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)$ may be expressed as a sum:
$$\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=
\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)
$$
where $y_1+\cdots +y_n=0$. Thus the vector $\vec{u}=\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)$ is orthogonal to the eigenspace for $\lambda=1$.  As $A$ is symmetric this means that $\vec{u}$ is a linear combination of eigenvectors for other eigenvalues.  If $n$ is odd these all have modulus less than $1$.  Thus:$$T^k \left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=
T^k\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
T^k\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)=
\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
T^k\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)\to \left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right)
$$
On the other hand, if $n$ is even, we have:
$$\left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=
\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)+\mu\left(\begin{array}{c}1\\-1\\\vdots\\-1\end{array}\right)
$$
with $\vec{u}=\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)$ a linear combination of eigenvectors with eigenvalue of modulus less than $1$.
Thus
$$T^{2k} \left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=
T^{2k}\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
T^{2k}\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)+\mu T^{2k}
\left(\begin{array}{c}1\\-1\\\vdots\\-1\end{array}\right)
\to \left(\begin{array}{c}\bar{x}+\mu\\\bar{x}-\mu\\ \vdots\\\bar{x}-\mu\end{array}\right)
$$
and
$$T^{2k+1} \left(\begin{array}{c}x_1\\x_2\\ \vdots\\x_n\end{array}\right)=
T^{2k+1}\left(\begin{array}{c}\bar{x}\\\bar{x}\\ \vdots\\\bar{x}\end{array}\right) +
T^{2k+1}\left(\begin{array}{c}y_1\\y_2\\ \vdots\\y_n\end{array}\right)+\mu T^{2k+1}
\left(\begin{array}{c}1\\-1\\\vdots\\-1\end{array}\right)
\to \left(\begin{array}{c}\bar{x}-\mu\\\bar{x}+\mu\\ \vdots\\\bar{x}+\mu\end{array}\right)$$
A: This sequence $(x_1,x_2,\cdots x_n)$ and its evolution can be modelized by a (column) vector $X_1$, becoming $X_2, X_3...$ when evoluting with the matrix vector relationship:
$$AX_k=AX_{k-1} \ \ \text{with} \ \ A := \frac12 \pmatrix{0&1 &&1 \\1&\ddots&\ddots \\&\ddots&&1\\1&&1&0}.$$
(as remarked by Ben Grossmann). More generally
$$A^{k}X_1=X_{k+1}$$
Matrix $A$ has many properties: (doubly) stochastic, symmetric, circulant. Its eigenvalues are known explicitly:
$$\lambda_k=\cos(2k\pi/n), \ \ k=1,2,...n$$
We have for all $k$, $|\lambda_k| \le 1$ with

*

*always one of them equal to $1$ (take $k=n$).


*one (and only one) of them equal to $-1$ which happens iff $2k\pi/n$ is equal to $\pi$, i.e., iff $n$ is even.
$A$ being symmetrical, its eigendecomposition can be written
$$A=P^T\Lambda P \ \ \text{giving} \ \ A^k=P\Lambda^k P^T$$
or expressed in a different way
$$A^k=\lambda_1^k V_1V_1^T+\lambda_2^k V_2V_2^T+... \lambda_n^k V_nV_n^T\tag{1}$$
Where the $V_k$s are the columns of $P$.
We can assume without loss of generality that $\lambda_1=1.$.
Therefore, if we aren't in the special case, all the other eigenvalues being such that $|\lambda|<1$, they are "dwarfed" by the first, and on the long term, there is a limit vector which is
$$\lim_{p \to \infty}X_{p+1}=\lim_{p \to \infty}A^pX_1=V_1V_1^TX_1$$
In the even case where there is an eigenvalue equal to $-1$, we have a second term, let us assume, WLOG again, that this eigenvalue is $\lambda_2$. In this case, for large values of $k$:
$$X_{p+1}=A^pX_1\approx V_1V_1^TX_1+(-1)^pV_2V_2^TX_1$$
giving an alternating behavior (see figure 2).

Fig. 1: Odd case $n=13$. Representation of the "profiles" of the $X_k$ on 400 iterations (Only one out of $5$ is represented), $X_1$ being a random vector. Convergence to a fixed vector.

Fig. 2: Even case $n=12$. Alternating behavior underlined by the choice of colors, alternating red and blue.
A: We use the constant $\omega:=e^{2\pi i/n}$ in order to form the Fourier transform $y$ of the vectors $x=(x_0,x_1,\ldots, x_{n-1})$:
$$y_j=\sum_{0\leq k< n} x_k\omega^{-jk}\qquad (0\leq j<n)\ .$$
We then have
$$(Ty)_j=\sum_{0\leq k< n}(Tx)_k\omega^{-jk}= \sum_{0\leq k< n}{x_{k-1}+x_{k+1}\over2}\omega^{-jk}=\ldots={\omega^j+\omega^{-j}\over2} y_j\ ,$$
so that
$$(Ty)_j=\cos\!{2\pi j\over n}\ \> y_j\qquad(0\leq j<n)\ .\tag{1}$$
When $n$ is odd then all $\left|\cos{2\pi j\over n}\right|<1$ $(0<j<n)$. It follows that
$$\lim_{r\to\infty}(T^r y)_j=0\qquad(j\ne0)\ .$$
Only $(T^r y)_0=\sum_k (T^r x)_k$ remains constant when $r$ increases. Inverting the Fourier transform we therefore can infer that all $(T^r x)_k$ converge to the arithmetic mean of the starting $x_k$.
When $n=2m$ is even then $(1)$ implies that $(Ty)_m=-y_m$. This shows that the alternating sum of the original $x_k$ is signchanged at each step, and keeps the original absolute value. If this alternating sum is not zero (by coincidence) we shall therefore see a limiting oscillating behavior. For a simple example consider the original sequence  $(1,-1,1,-1,\ldots, 1,-1)$.
