Question regarding on powers of a certain matrix I am a high school student who is interested in mathematics, and I'm stuck on a problem while doing a small investigation (too small to be called "research").
Problem: what is the sum of all elements of $n \times n$ matrix $M^m$, where $M_{ij} = \begin{cases} 0, & j > i + 1 \\ 1, & j \le i + 1 \end{cases} ?$
Although answers in terms of $m, n$ are better, other forms would help.
Thanks in advance!
 A: I had an idea inspired by the answer of @gabriel-ribeiro.
Let us find the characteristic polynomial of the matrix $M$,  ie $D_n \equiv det(M-\lambda I)$, for a given dimension $n$. Once we find it, we can write powers of the matrix $M$ as a linear combination of lower powers and apply the summation over the all elements to all matrices in the equality.
If you write the determinant using the usual rule with the coefficients on the last column (which are all null, but last two), you get a recursion: $$D_{n+1}=-\lambda(D_n+D_{n-1} \;)$$ with $D_0=1, D_1=1-\lambda, D_2=\lambda^2-2\lambda,D_3=-\lambda^3+3\lambda^2-\lambda$, etc. 
Let us note that you can actually solve in closed form for $D_n(\lambda)$! Unfortunately, it appears that the number of powers of $\lambda$ increases with the matrix dimension $n$.
Let us reproduce the result of @gabriel-ribeiro for $n=3$ to make the method clearer:
we start by noting that the characteristic polynomial is $-\lambda^3+3\lambda^2-\lambda$ and we know that if we replace $\lambda$ by the matrix $M$ we get zero: $$M^3=3M^2-M$$ (I arranged the terms a bit). Using the same notation as @gabriel-ribeiro ($f(m)=\sum M^m$, where the sum if over all elements of the matrix) and summing over the previous equation (after we multiply by $M^{m-3}$ $\;$): $$f(m)=3f(m-1)-f(m)$$, which is a linear recursion that can be solved analytically (we need just the two starting terms).
Let us try to reproduce Gabriel Ribeiro's result for $n=3$, where $f(1)=8, f(2)=21$ and the recursion gives $$f(n=3;m) = \frac{15+7\sqrt{5}}{10} \;\; (\frac{3+\sqrt{5}}{2}\big)^m+\frac{15-7\sqrt{5}}{10} \; \; (\frac{3-\sqrt{5}}{2})^m$$, which is the same result as found by Gabriel Ribeiro! Now, one can deduce it for arbitrary matrix dimension, after computing the first two terms in the recursion.
For $n=$ the characteristic polynomial still has three terms, so we can repeat the same method, BUT for $n=5$ it has four terms and our recursion has now a higher order. It can be solved analytically nonetheless (we can find the polynomial for arbitrary matrix dimension), but more and more starting values are required, and those may be cumbersome to compute.
This as as far as I got. Maybe there are some properties of your matrix that can make it possible to compute what you look for (taking into account the special form of your matrix). For example, if you can compute the eigenvalues and eigenvectors, you can write the results immediately. Numerically, that is what I would do.
Hope this helps you a bit.
A: It is the number of walks of length $2(m+1)+n$ in the path graph $P_{n+1}$ from one end to the other cf. OEIS A005023 (when $n=7$) 
https://oeis.org/search?q=34%2C+143%2C+560%2C+2108%2C+7752&language=english&go=Search
A procedure in Maple is as follows (it generalizes that given in the reference). We give $n$ and the obtained sequence begins with $m=0,m=1,\cdots$.
restart:
n := 9:
a := proc (k) options operator, arrow; sum(binomial(n+2*k, (n+2)*j+k-2), j = ceil((2-k)/(n+2)) .. floor((n+2+k)/(n+2)))-(sum(binomial(n+2*k, (n+2)*j+k-1), j = ceil((1-k)/(n+2)) .. floor((n+1+k)/(n+2)))) end proc:
seq(a(k), k = 1 .. 10);
9, 53, 260, 1156, 4845, 19551, 76912, 297275, 1134705, 4292145
EDIT. Clearly, the OP read this in a book about graphs; he was careful to not describe the context of the question; I think that he (she) is a joker.


*

*Def. The path graph $P_k$ is defined by the matrix $G_k=J_k+{J_k}^T$ where $J_k$ is the nilpotent Jordan block of dimension $k$. There are $k$ states $1,\cdots,k$ and the passage of time $t$ to $t + 1$ is given by the signum $+$ (right shift) or $-$ (left shift). The number of walks of length $2(m+1)+n$, in the path graph $P_{n+1}$ from state $1$ to $n+1$, is $f(m,n)={{G_{n+1}}^{2(m+1)+n}}_{1,n+1}$. (here, a walk is a sequence of $+,-$ with $(n+m+1) "+"$ and $(m+1) "-"$, beginning and ending with $+$).


Proposition 1. If $m\geq 1$, then $f(m,n)=\sum_{j=a}^b \binom{n+2(m+1)}{(n+2)j+m-1}-\sum_{j=c}^d\binom{n+2(m+1)}{(n+2)j+m}$ where $a=ceil(\dfrac{1-m}{n+2}),b=floor(\dfrac{n+m+3}{n+2}),c=ceil(\dfrac{-m}{n+2}),d=floor(\dfrac{n+m+2}{n+2})$.
Proof. cf. the above reference.


*In our problem, the matrix $M_n$ is associated to some graph $Q_n$; $\sum_{i,j}{M^m}_{i,j}$ is the number of walks de length $m$ in $Q_n$, denoted by $g(m,n)$.

*Proposition 2. $f(m,n)=g(m,n)$.
Proof. It is a numerical evidence ; yet I have no proof and I do not have time to look for one.
A: Let $f(m)$ denotes the sum of all entries of $M^m$. I can only obtain a linear recurrence relation for $f$.
Let $e$ be the all-one vector and $E=ee^T$ be the all-one matrix. Let also $B=E-M$. Then $B^{\lceil n/2\rceil}=0$ and one can prove by mathematical induction (or by setting up and solving a linear recurrence relation) that the sum of all elements of $B^k$ is equal to $g(k)=\binom{n-k}{k+1}$ when $k\le\lceil \frac n2\rceil-1$. Now
\begin{align*}
f(m+1) &= e^T(E-B)^{m+1}e
=\operatorname{tr}\left[ee^T(E-B)^{m+1}\right]\\
&=\operatorname{tr}\left[E(E-B)^{m+1}\right]\\
&=\operatorname{tr}\left[E^2(E-B)^m - EB(E-B)^m\right]\\
&=\operatorname{tr}\left[E^2(E-B)^m - EBE(E-B)^{m-1} + EB^2(E-B)^{m-1}\right]\\
&=\operatorname{tr}\left[E^2(E-B)^m - EBE(E-B)^{m-1} + EB^2E(E-B)^{m-2} - EB^3(E-B)^{m-3}\right]\\
&=\ldots
\end{align*}
Since $B^{\lceil n/2\rceil}=0$ and $EB^kE=g(k)E$, it follows that for each $m\ge \lceil \frac n2\rceil$, we have
$$
f(m+1)
= n\,f(m) + \sum_{k=1}^{\lceil n/2\rceil-1} (-1)^k \binom{n-k}{k+1}\ f(m-k).\tag{$\ast$}
$$
In particular, we have
$$
f(m+1)=
\begin{cases}
2f(m) &\text{when } n=2;\\
3f(m)-f(m-1)&\text{when } n=3;\\
4f(m)-3f(m-1)&\text{when } n=4.
\end{cases}
$$
So, for any fixed $n$, you may first calculate the values of $f(1)$ up to $f(\lceil n/2\rceil)$ directly and then solve the homogeneous linear recurrence relation $(\ast)$ as usual. For $n=2,3,4$, we get
$$
f(m)=
\begin{cases}
2^{m+1} &\text{when } n=2;\\
\frac{15+7\sqrt{5}}{10} \left(\frac{3+\sqrt{5}}{2}\right)^m+\frac{15-7\sqrt{5}}{10} \left(\frac{3-\sqrt{5}}{2}\right)^m
&\text{when } n=3;\\
\frac12(3^{m+2}-1)&\text{when } n=4.
\end{cases}
$$
This at least explains the recurrence relations found by Gabriel Ribeiro and Chip in their answers. You may verify whether loup blanc's proposed solution satisfies $(\ast)$ or not.
A: I did a few particular cases. (It's not hard to prove them using induction on $m$.)


*

*$n=1$: $$\sum_{i=1}^n \sum_{j=1}^n (M^m)_{ij}=1.$$

*$n=2$: $$\sum_{i=1}^n \sum_{j=1}^n (M^m)_{ij}=2^{m+1}.$$

*$n=3$: $$\sum_{i=1}^n \sum_{j=1}^n (M^m)_{ij}=\frac{15+7\sqrt{5}}{10}\left(\frac{3+\sqrt{5}}{2}\right)^m+\frac{15-7\sqrt{5}}{10}\left(\frac{3-\sqrt{5}}{2}\right)^m.$$

*$n=4$:  $$\sum_{i=1}^n \sum_{j=1}^n (M^m)_{ij}=\frac{3^m -1}{2}.$$


The Fibonacci sequence appears almost everywhere here, so it isn't very hard to find patterns for each fixed $n$. But I can't seem to find anything else.
