1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple linear algebra proof

  1. Feb 10, 2014 #1
    1. The problem statement, all variables and given/known data

    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

    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:

    [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] 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. jcsd
  3. Feb 10, 2014 #2
    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.
     
  4. Feb 10, 2014 #3
    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
     
  5. Feb 10, 2014 #4
  6. Feb 10, 2014 #5

    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Simple linear algebra proof
Loading...