In my book the author claims that number of multiplications required find determinant of a $n \times n$ matrix by cofactor is $$\sum^n_{k =1} \dfrac{n!}{k!}.$$
Let $f(n)$ is number of multiplications required for find determinant of $n\times n$ matrix.
Cofactor expansion of determinant of $A_{n \times n}$ along $j$th row is $$\det A = \sum_{k=1}^n a_{j,k} (-1)^{j+k} \det A_{j,k}$$ where $A_{j,k}$ is the matrix formed by removing row $j$ and column $k$ of $A$.
Number of multiplication required to calculate $\det A_{j,k}$ is $f(n-1)$. Since there are $n$ terms in the cofactor expansion and each term has $2$ multiplication.
Also, by manual calculation I know $f(2) = 3$
Therefore I get $f(n) = n(f(n-1) + 2)$.
I used Wolfram Alpha to solve for $f(n)$, it spits out $$f(n) = 2 \mathbf e n \Gamma (n,1) – \dfrac52 \Gamma(n+1).$$
I will not pretend that I know gamma function and incomplete gamma function. I honestly have no clue.
Where did I make mistake ? How can I get the formula given in the book ?
Best Answer
I believe the recurrence should be $f(n)=n(f(n-1)+1)$ with $f(2)=2.$ You can absorb the $(-1)^{j+k}$ in the addition of the products, so each term just takes one multiply. This gives $0,2,9,40,205,1236$, which is OEIS A038156 and matches your author's expression except that the upper limit of the sum should be $n-1$, not $n$. Another formula is $f(n)=\lfloor n!(e-1) \rfloor -1$
We can verify your author's formula from the recurrence by induction. The base case $f(2)=2=2!\frac 1{1!}$ works. Now assume we have $f(n)=n!\sum_{k=1}^{n-1}\frac 1{k!}$ We have $$\begin {align} f(n+1) &=(n+1)\left(f(n)+1\right)\\ &=(n+1)\left(n!\sum_{k=1}^{n-1}\frac 1{k!}+1\right)\\ &=(n+1)!\left(\sum_{k=1}^{n-1}\frac 1{k!}+ \frac 1{n!}\right)\\ &==(n+1)!\left(\sum_{k=1}^{n}\frac 1{k!}\right) \end {align}$$