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 &amp; 1&amp; 1\\ <br /> 0&amp; 1&amp; 1\\ <br /> 0&amp; 0 &amp; 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 &amp; 2&amp;3\\ <br /> 0&amp; 1&amp; 2\\ <br /> 0&amp; 0 &amp; 1<br /> \end{bmatrix}

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

a^4 = \begin{bmatrix}<br /> 1 &amp; 4&amp; 10\\ <br /> 0&amp; 1&amp; 4\\ <br /> 0&amp; 0 &amp; 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 &amp; n &amp; n+ \sigma\\ <br /> 0 &amp; 1 &amp; n\\ <br /> 0&amp; 0 &amp; 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 &amp; n &amp; \frac{n(n+1)}{2} \\ <br /> 0&amp; 1&amp; n\\ <br /> 0&amp;0 &amp; 1<br /> \end{bmatrix}

and then is just using induction

thanks a lot!