# Simple linear algebra proof

1. Feb 10, 2014

### U.Renko

1. The problem statement, all variables and given/known data

find a formula for $\begin{bmatrix} 1 & 1& 1\\ 0& 1& 1\\ 0& 0 & 1 \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

2. Relevant equations

3. 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} 1 & 2&3\\ 0& 1& 2\\ 0& 0 & 1 \end{bmatrix}$

$A^3 = \begin{bmatrix} 1 & 3& 6\\ 0& 1& 3\\ 0& 0 & 1 \end{bmatrix}$

$a^4 = \begin{bmatrix} 1 & 4& 10\\ 0& 1& 4\\ 0& 0 & 1 \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$ thats 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.

Last edited: Feb 10, 2014
2. Feb 10, 2014

### 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.

3. Feb 10, 2014

### 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
if n=3
if n=4

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} 1 & n & n+ \sigma\\ 0 & 1 & n\\ 0& 0 & 1 \end{bmatrix}$

that is where I thought was too cumbersome and was wondering if there is a simpler way

4. Feb 10, 2014

### kduna

5. Feb 10, 2014

### U.Renko

well, indeed it is.

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

and then is just using induction

thanks a lot!