How to calculate power series with a large norm matrix. Take this matrix representing the Markov map for seeing a Heads followed by a Tails in a sequence of fair coin flips:
$$M = \begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 \\  \frac{1}{2} & 0 & \frac{1}{2}  \\ 0 & 0 & 1 \end{pmatrix}$$
Since the final state is absorbing we can reason that $$\lim_{n\rightarrow \infty} M^n = L = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$$
I am interested in the following limit of a sum for matrices like this.
$$\lim_{n \rightarrow \infty } \left( n M^n - \sum_{i=0}^{n-1}M^i \right)$$
It would seem that I can easily replace $M^n$ with $L$ in the first term but what to do with the actual sum bit??
Ordinarily I'd look at that and think of the power series, except that the norm of $M$ is too big for that to work.
It seems (from empirical evidence) that in this case I get
$$ \lim_{n \rightarrow \infty} \sum_{i=0}^{n-1}M^i = \begin{pmatrix} 4 & 2 & n-6 \\ 2 & 2 & n-4 \\ 0 & 0 & n \end{pmatrix}$$
This means that I can do the limit from above, indeed I get
$$ \lim_{n \rightarrow \infty } \left( n M^n - \sum_{i=0}^{n-1}M^i \right) = \begin{pmatrix} -4 & -2 & 6 \\ -2 & -2 & 4 \\ 0 & 0 & 0 \end{pmatrix}$$
But how can I do this in general (without a lot of numerical computation each time)? I've tried a few different such Markov maps and I always seem to get convergence even though my matrices always have a norm larger than one. I'd appreciate some help!
Thanks in advance.
UPDATE:
See greg's post below. Basically if we assume there is a limit (say $S$ for the limit of the partial sums) we can do the following:
$$ n M^n -  \sum_{i=0}^{n-1}M^i = \sum_{i=0}^{n-1}  (M^n - M^i) $$
Then 
$$ S = \lim_{n\rightarrow \infty} \sum_{i=0}^{n-1}  (M^n - M^i) $$
If you take that equation and multiply by $M$ and subtract $I$ you get
$$ S - L = M S - I \Rightarrow (M - I)S = I - L$$
which is the same as what greg had. The problem is that you can't always take the inverse of $(M-I)$; in the cases I considered it is singular.
At this point I noticed that I can always expect the last row of $S$ to be the zero vector as long as $M$ is indeed a right stochastic matrix (as is the case for what I'm doing). In fact the last row of $M$ in an absorbing Markov map is always going to be ${0,\ldots,0,1}$.
So in some sense I'm really mostly interested in the upper rows of the matrix $M$.
Introduce $T$ where $T$ is the identity matrix with the last row zeroed out.
$$ T =  \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$
Then $ S = T S $ and we can replace $M \rightarrow T M$ and $ L \rightarrow T L$
and follow the above logic to get
$$ (T M - I) S =  T - T L = I - L $$
Now we can invert $(T M - I)$ and solve for the limit $S$
$$ S = (T M - I)^{-1} (I - L) $$
I don't know why $(T M - I)$ should always be non-singular but it worked for me for many different choices of $M$ as right-stochastic matrices with the last row ending with one.
I feel like I've answered my own question, although greg's post contains most of this information (before I had a chance to write this all down).
 A: Go ahead and substitute $L$, and your sum becomes
$$
\sum_{i=0}^{n-1} (L-M^i)
$$
There is some finite index $k$ for which $M^k$ is indistinguishable from $L$.  So terms beyond that index will contribute nothing to the sum.  Once you determine what the cut-off value is, you are left with a finite summation
$$
\sum_{i=0}^{k} (L-M^i)
$$
Update
Denote the $k^{th}$ partial sum as
$$
 S_k = \sum_{i=0}^{k} (L-M^i)
$$
Using the fact that $ML=LM=L$ we easily find that $LS_k=S_kL=0$. 
With a little more effort we can find
$$ \eqalign{
 S_kM = MS_k &= M\sum_{i=0}^{k} (L-M^i) \cr
   &= \sum_{i=0}^{k} (LM-M^{i+1}) \cr
   &= \sum_{i=1}^{k+1} (L-M^{i}) \cr
   &= (L-M^{k+1}) - (L-I) + \sum_{i=0}^{k} (L-M^i) \cr
   &= (I-L) + S_k \cr
}$$
where $L=M^{k+1}$ for a large enough $k$.
Finally we can solve for $S_k$
$$ \eqalign{
  (M-I)S_k &= (I-L) \cr
  S_k &= (M-I)^{+}(I-L) \cr
}$$
This should be the solution, but the solution found in the problem statement turns out to be this 
$$ \eqalign{
  S_k &= (I-L)(M-I)^{+}(I-L) \cr
}$$
But I don't see why I'm required to multiply by $(I-L)$.
