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

[U.Renko]

Homework Statement

find a formula for [itex] \begin{bmatrix}
1 & 1& 1\\
0& 1& 1\\
0& 0 & 1
\end{bmatrix} ^n[/itex]

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:

[itex] A^2 = \begin{bmatrix}
1 & 2&3\\
0& 1& 2\\
0& 0 & 1
\end{bmatrix} [/itex]

[itex] A^3 = \begin{bmatrix}
1 & 3& 6\\
0& 1& 3\\
0& 0 & 1
\end{bmatrix} [/itex]

[itex] a^4 = \begin{bmatrix}
1 & 4& 10\\
0& 1& 4\\
0& 0 & 1
\end{bmatrix} [/itex]


so the pattern is :
below the diagonal is always 0
the diagonal is always 1
[itex] a_12 = a_23 = n [/itex]
[itex] a_13 = some number [/itex] 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 [itex]a_{1,3}[/itex] came up in the matrices:
following the multiplicattion of matrices procedure.
it is the sum of [itex] 1*1 + 1*(n-1) [/itex] plus 1 times the [itex]a_{1,3} [/itex] element of the [itex]A^{n-1}[/itex] 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 [itex]a_{13} [/itex] of [itex] A^n[/itex] is always [itex] 1 + (n-1) + something[/itex]

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
[itex] n + \sigma [/itex] where [itex]\sigma = \sum_{i=1}^{n-1}i[/itex] the formula asked then becomes: [itex] \begin{bmatrix}
1 & n & n+ \sigma\\
0 & 1 & n\\
0& 0 & 1
\end{bmatrix}[/itex]that is where I thought was too cumbersome and was wondering if there is a simpler way

 

[kduna]

[itex] n + \sigma [/itex] where [itex]\sigma = \sum_{i=1}^{n-1}i[/itex]

Isn't [itex] n + \sigma = \sum_{i=1}^n i[/itex]?

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 [itex] n + \sigma = \sum_{i=1}^n i[/itex]?

well, indeed it is.

so now the formula becomes [itex]A^n = \begin{bmatrix}
1 & n & \frac{n(n+1)}{2} \\
0& 1& n\\
0&0 & 1
\end{bmatrix}[/itex]

and then is just using induction

thanks a lot!