Results 1 to 2 of 2

Math Help - Proof by induction

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    96

    Proof by induction

    i need to prove this by induction...
    N(sub k) is the number of flops needed to compute the determinant of a k x k matrix. N(1) = 0, N(2) = 3, N(3) = 14
    Prove: N(k) = ((N(k-1)+2)*k)-1

    I set it up so that
    N(k-1) = ((N(k-2)+2)*(k-1))-1 for a (k-1) x (k-1) matrix
    But now I'm sort of stuck, and am unsure about how to go about reaching the original equation
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mistykz View Post
    i need to prove this by induction...
    N(sub k) is the number of flops needed to compute the determinant of a k x k matrix. N(1) = 0, N(2) = 3, N(3) = 14
    Prove: N(k) = ((N(k-1)+2)*k)-1

    I set it up so that
    N(k-1) = ((N(k-2)+2)*(k-1))-1 for a (k-1) x (k-1) matrix
    But now I'm sort of stuck, and am unsure about how to go about reaching the original equation
    You need to know the algorithm being used, the usual hand method of expanding by cofactors computes a (n+1)x(n+1) determinant as (n+1) nxn determinants. If this is the algorithm you are analysing you have:

    N(n+1)=(n+1)N(n)

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum