How Can You Derive the Formula for the nth Power of a Triangular Matrix?

[U.Renko]

Homework Statement

find a formula for $\begin{bmatrix}<br /> 1 & 1& 1\\ <br /> 0& 1& 1\\ <br /> 0& 0 & 1<br /> \end{bmatrix} ^n$

and prove it by induction


the induction part is ok.
I'm just having trouble finding a pattern
I may have figured it out but it looks too cumbersome

Homework Equations

The Attempt at a Solution

Lets call that matrix A

I computed A^2 through A^5 and noticed a pattern:

$A^2 = \begin{bmatrix}<br /> 1 & 2&3\\ <br /> 0& 1& 2\\ <br /> 0& 0 & 1<br /> \end{bmatrix}$

$A^3 = \begin{bmatrix}<br /> 1 & 3& 6\\ <br /> 0& 1& 3\\<br /> 0& 0 & 1<br /> \end{bmatrix}$

$a^4 = \begin{bmatrix}<br /> 1 & 4& 10\\ <br /> 0& 1& 4\\ <br /> 0& 0 & 1<br /> \end{bmatrix}$


so the pattern is :
below the diagonal is always 0
the diagonal is always 1
$a_12 = a_23 = n$
$a_13 = some number$ that's where I had trouble figuring the pattern

I noticed that, it is also the sum of the elements in the first row of A^(n-1) but that is a bit awkward to generalize.

 

[kduna]

This is a fun little problem, just do the computation for a couple small n and the the pattern should be easy to pick out.

 

[U.Renko]

ok, here is what I've done and why I said it looked cumbersome

I thought about how $a_{1,3}$ came up in the matrices:
following the multiplicattion of matrices procedure.
it is the sum of $1*1 + 1*(n-1)$ plus 1 times the $a_{1,3}$ element of the $A^{n-1}$ matrix.

thus
if n=2
we add 1+1+1=3
if n=3
we add 1+2+3=6
if n=4
we add 1+3+6=10

so, the element $a_{13}$ of $A^n$ is always $1 + (n-1) + something$

then I took as an example n =4
in this case we have
1+ (4-1) + [1+(4-2) +[1 +(4-3) +[ 1 +[4-4] ] ] ]
in other words
1+ 3+ 1 + 2 + 1+1+1
which is:
4 + (1+2+3)
which I expressed as
$n + \sigma$ where $\sigma = \sum_{i=1}^{n-1}i$ the formula asked then becomes: $\begin{bmatrix}<br /> 1 & n & n+ \sigma\\ <br /> 0 & 1 & n\\ <br /> 0& 0 & 1<br /> \end{bmatrix}$that is where I thought was too cumbersome and was wondering if there is a simpler way

 

[kduna]

$n + \sigma$ where $\sigma = \sum_{i=1}^{n-1}i$

Isn't $n + \sigma = \sum_{i=1}^n i$?

There is a nice formula for the sum of the numbers 1 through n. :)

http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

 

[U.Renko]

Isn't $n + \sigma = \sum_{i=1}^n i$?

well, indeed it is.

so now the formula becomes $A^n = \begin{bmatrix}<br /> 1 & n & \frac{n(n+1)}{2} \\ <br /> 0& 1& n\\ <br /> 0&0 & 1<br /> \end{bmatrix}$

and then is just using induction

thanks a lot!