# Proof by induction

• Sep 19th 2008, 09:59 AM
mistykz
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
• Sep 19th 2008, 12:11 PM
CaptainBlack
Quote:

Originally Posted by mistykz
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