Powers of a simple matrix and Catalan numbers Consider $m \times m$ anti-bidiagonal matrix $M$ defined as:
$$M_{ij} = \begin{cases}
      -1, & i+j=m\\
\,\,\  1, & i+j=m+1\\
\,\,\, 0, & \text{otherwise}
\end{cases}$$
Let $S_n$ stand for the sum of all elements of the $n$-th power of the matrix:
$$S_n=\sum_{ij}\left(M^n\right)_{ij}.$$
Prove that for integer $0 < k < m$:


*

*$S_{2k}=C_{k-1}$, where $C_k$ is $k$-th Catalan number;

*$S_{2k+1}=0$,
and, additionally,


*$S_{2m+1}=(-1)^{m-1}$.


PS: In fact, the first equality holds much longer up to $k=2m$. Besides $S_{4m+2}=C_{2m}-1$.
 A: Acknowledgement
The idea of the proof and especially the closed form (2) are due to darij grinberg.
Preliminaries
Let numbers $b^n_i$, where $n$ and $i$ are integer numbers ($n>0$), be given by recurrence relation:
$$(1)\quad
b^1_i=\delta_{0i}+\delta_{1i},\quad 
b^{n+1}_i=
\begin{cases}
b^n_i-b^n_{i-1},&n \text{ even }\\
b^n_i-b^n_{i+1}, &n \text{ odd }
\end{cases}.
$$
Then the following explicit expression applies:
$$(2)\quad
b^n_i=(-1)^{i}\left[
\binom{n-1}{\left\lfloor\frac{n-1}{2}\right\rfloor-i}-
\binom{n-1}{\left\lfloor\frac{n+1}{2}\right\rfloor-i}
\right].
$$
For $n=1$ the statement is obviously valid. Substituting (2) into right-hand side of (1) separately for odd and even $n$ one ends up with the same expression (2) upon replacement of $n$ with $n+1$. 
The following observations are important:
$$
\begin{align}
&(2a)\quad b^n_0=0, \text{ for even } n;\\
&(2b)\quad b^n_1=C_{\frac{n-1}{2}}, \text{ for odd } n;\\
&(2c)\quad b^n_i=0,\text{ for } i>\left\lfloor\frac{n+1}{2}\right\rfloor.
\end{align}$$
Proof of the claims
It is convenient to introduce besides matrix $M$ the antidiagonal matrix $\Gamma$:
$$\varGamma=\begin{cases}
1, &i+j=m+1\\
0, &\text{otherwise}
\end{cases},$$
and construct the matrices $L_n=\varGamma^n M\varGamma^{n-1}$ and ${\cal L}_n: \{{\cal L}_1=L_1;\ {\cal L}_n=L_n{\cal L}_{n-1}\}$.
$L_n$ is lower- or upper-bidiagonal matrix for odd and even $n$, respectively. The diagonal elements are $1$ and subdiagonal (or, respectively, superdiagonal) elements are $-1$. Note that due to identity $\varGamma^2=I$ the following equality holds:
$$
{\cal L}_n=\varGamma^n M^n.
$$
Thus the action of ${\cal L}_n$ on a vector is up to permutation of elements equivalent to action of $M^n$.
Consider now the vectors
$u^{n}={\cal L}_n u$, where $u$ is $m$-dimensional "all-ones" vector. Then the following recurrence relation holds for any $i=1\dots m$ and any $n>0$:
$$(3)\quad
u^{1}_i=(L_1u)_i=\delta_{1i},\quad 
u^{n+1}_i=(L_{n+1}u^n)_i=
\begin{cases}
u^n_i-u^n_{i-1},&n \text{ even }\\
u^n_i-u^n_{i+1}, &n \text{ odd }
\end{cases},
$$
with a convention $u^n_0=0$ and $u^n_{m+1}=0$.
Now observe strong resemblance of (3) and (1). The fact that $u^n_0\ne b^n_0$ for odd $n$ does not matter as $u^n_0$ enters the recursion only for even $n$. One concludes that $u^n_i=b^n_i$ for all $i=1\dots m$ as long as $b^{n-1}_{m+1}=0$ for even $n$, which fails firstly for $n=2m+2$.
Thus:
$$
\forall i=1\dots m, \forall n=1\dots (2m+1):\quad u^n_i=b^n_i.
$$
The completion of the proof is easy. In fact:
$$
(4)\quad S_n=uM^nu=u{\cal L}_nu=\sum_{i=1}^m u^{n}_i=\begin{cases}
u^{n-1}_m,& n\text{ odd }\\
u^{n-1}_1,& n\text{ even }
\end{cases}.
$$
For $n\le2m+1$ the equation amounts to:
$$
\text{for odd } n:\quad S_n= 
b^{n-1}_m=\begin{cases}
0, &n<2m+1\\
(-1)^{m+1}, & n=2m+1
\end{cases};
$$
$$
\text{for even } n:\quad S_n=b^{n-1}_{1}=C_{\frac{n}{2}-1}.
$$
Thus all three claims of the question are proved.
Concluding remark
One may wonder why the equality $S_{2k}=C_{k-1}$ holds for much higher values of $k$ (up to $2m$). The reason is seen from the equality (4). As the $u^n$-vector starts "corrupting" from the end, it requires additional $2m$ recursion steps till $u^n_1$ starts deviating from $b^n_1$. To be more specific the equality $u^n_i=b^n_i$ holds up to $n=2(2m-i)+1$.
