# Formula for $n$th power of a matrix that is upper triangular all $2$'s except $1$ at position $(1,1)$

Let $$B_k$$ be the $$k \times k$$ upper triangular matrix of all $$1$$'s, i.e

$$B_k = \begin{pmatrix} 1 & 1 & \dots & 1 \\ 0 & 1 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{pmatrix} = \sum_{i=1}^k\sum_{j=i}^k {\bf e_ie_j}^T$$

And let

$$T_k = 2B_k - {\bf e_1e_1}^T = \begin{pmatrix} 1 & 2 & \dots & 2 \\ & 2 & \dots & 2 \\ & & \ddots & \vdots \\ & & & 2 \end{pmatrix}$$

Is there a (fast) formula for the $$(1, j)$$ entry of $$T_k^n$$

My attempt:

Write $$T_k$$ in block form

$$T_k = \left(\begin{array}{r|r} 1 & {\bf 2}^T \\ \hline & 2B_{k-1} \end{array}\right)$$

And we have (I leave out the lower index on $$B$$) $$T_k^n = \left(\begin{array}{r|r} 1 & {\bf 2}^T \sum_{p=0}^{n-1}(2B)^p \\ \hline & 2^nB^n \end{array}\right) = \left(\begin{array}{r|r} 1 & {\bf 2}^T (I-(2B)^n)(I-2B)^{-1} \\ \hline & (2B)^n \end{array}\right)$$

Now $$(B^n)_{ij} = {n-1+j-i\choose n-1}$$ and I believe it isn't too hard to prove that

$$(I-2B)^{-1} = \begin{pmatrix} -1 & 2 & -2 & 2 &\dots \\ & -1 & 2 & -2 & \dots \\ & & -1 & 2 & \\ & & & \ddots & \vdots \\ & & & &-1 \end{pmatrix}$$

So for the $$j$$th element of the top right block, call it $$c_j$$, we get the formula

$$c_j = 2^{n+1}\left(\sum_{u=1}^j \sum_{v=u}^j {n-1+v-u \choose n-1}(-1)^{j-v}(2-\delta_{jv})\right) - 2\sum_{v=1}^j (-1)^{j-v}(2-\delta_{jv})$$

But is there a nicer expression for this? Wolfram Alpha seems to suggest some sort of hypergeometric function for the first sum but is that any feasible to calculate?

By the way, numerical evidence indicates that the sum of the first row of $$T_k^n$$ has the generating function $$\frac{1}{(1-x)(1-2x)^{k-1}}$$. Is this true? It would make sense since it's the characteristic polynomial of $$T_k$$ in the denominator.

Note: This is related to this question where $$T_k$$ appears as a block in a bigger matrix $$A_k$$. Using block calculations we get a formula for the sought after quantity involving powers of $$T_k$$ and $$A_{k-1}$$ ($$A_{k-1}$$ lies as a block in bottom right corner of $$A_k$$), and that big rectangular block so the calculations will still be slow if done by matrix multiplication, but maybe if we have a good formula, it can somehow simplify.

EDIT:

With JBL's answer (switching sum order and using hockey stick formula) we have

$$c_j = 2^{n+2}(-1)^j \left( \sum_{v=1}^j (-1)^v {n+v-1 \choose v-1} \right) - 2^{n+1}{n+j-1 \choose j-1} + 2(-1)^j$$

The double sum will certainly get simpler if you reverse the order of summation and use the hockey-stick identity, but the simplified form (with an alternating sum of binomial coefficients) doesn't go away. The second (single) sum can easily be simplified (actually it's a very complicated way of writing $$(-1)^{j + 1}$$).