Here is Prob. 20, Sec. 2.2, in the book Linear Algebra With Applications by Steven J. Leon and Lisette de Pillis, tenth edition:
Show that evaluating the determinant of an $n \times n$ matrix by cofactors involves ( $n! - 1$ ) additions and $\sum_{k=1}^{n-1} n! / k!$ multiplications.
My Attempt:
Let $s_n$ and $m_n$ be the total numbers of additions (along with subtractions) and the total numbers of multiplications, respectively, involved in evaluating the determinant of an $n \times n$ matrix.
Method 1.
For $n = 1$, we have $$ \det \big( [ \begin{matrix} a \end{matrix} ] \big) = a. $$ So we have $$ s_1 = 0 = 1! - 1 \tag{1} $$ and $$ m_1 = 0 = \sum_{k=1}^{1-1} \frac{1!}{k!}. \tag{2} $$ Thus our results hold for $n=1$.
Now suppose that, for any given $n = 1, 2, 3, \ldots$, we have $$ s_n = n!-1 \qquad \mbox{ and } \qquad m_n = \sum_{k=1}^{n-1} \frac{n!}{k!}. $$
Let $A$ be an $(n+1) \times (n+1)$ matrix. Then by using the cofactor expansion along the $i$th row of $A$, we have $$ \det (A) = a_{i1} A_{i1} + \cdots + a_{in}A_{in} + a_{i, n+1} A_{i, n+1}. \tag{1} $$
Now in the expression on the right-hand-side of (1), there are $n+1$ determinants of size $n \times n$, namely, $A_{ij}$ for each $j = 1, \ldots, n, n+1$. Each of these determinants involves ($n!-1$) additions and $\sum_{k = 1}^{n-1} n!/k!$ multiplications by virtue of our induction hypothesis. Moreover, in evaluating $\det (A)$ we need to perform an additional $n$ additions and an additional $n+1$ multiplications.
Therefore we have $$ \begin{align} s_{n+1} &= n + (n+1) (n! - 1) \\ &= n + (n+1) n! - (n+1) \\ &= (n+1)! - 1, \end{align} $$ and also $$ \begin{align} m_n &= (n+1) + (n+1) \sum_{k=1}^{n-1} \frac{n!}{k!} \\ &= \frac{(n+1)!}{n!} + \sum_{k=1}^{n-1} \frac{ (n+1) n! }{ k!} \\ &= \frac{(n+1)!}{n!} + \sum_{k=1}^{n-1} \frac{ (n+1)! }{ k!} \\ &= \sum_{k=1}^n \frac{ (n+1)! }{ k!} \\ &= \sum_{k=1}^{ (n+1) -1 } \frac{ (n+1)! }{ k!}, \end{align} $$ as required.
Is this proof correct and clear enough?
Method 2.
For each $n = 2, 3, 4, \ldots$, if $A$ is an $n \times n$ matrix, then we have $$ \det (A) = \sum_{j = 1}^n a_{ij} A_{ij}. $$ Thus we have the recursive relations $$ s_n = (n-1) + n s_{n-1} \qquad \mbox{ and } \qquad m_n = n + n m_{n-1}. $$ Moreover, we also have $s_1 = 0$ and $m_1 = 0$. [Refer to (1) and (2) above.]
Backtracking, we obtain $$ \begin{align} s_n &= (n-1) + n s_{n-1} \\ &= (n-1) + n \left( (n-1-1) + (n-1) s_{n-2} \right) \\ &= (n-1) + n(n-2) + n(n-1) s_{n-2} \\ &= (n-1) + n(n-2) + n(n-1) \left( (n -2-1) + (n-2) s_{n-3} \right) \\ &= (n-1) + n(n-2) + n(n-1)(n-3) + n(n-1)(n-2) s_{n-3} \\ &= \ldots. \end{align} $$
Is this calculation correct and accurate? If so, then how to proceed from here?
We also have $$ \begin{align} m_n &= n + n m_{n-1} \\ &= n + n \left( (n-1) + (n-1) m_{n-2} \right) \\ &= n + n(n-1) + n(n-1) m_{n-2} \\ &= n + n(n-1) + n(n-1) \left( (n-2) + (n-2) m_{n-3} \right) \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2) m_{n-3} \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2) \left( (n-3) + (n-3) m_{n-4} \right) \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2) (n-3) + n(n-1)(n-2) (n-3) m_{n-4} \\ &= \ldots \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \cdots + n(n-1)(n-2)(n-3)\cdots \big(n - (n-1) \big) + n(n-1)(n-2)(n-3)\cdots \big(n - (n-1) \big) m_{n - (n-1)} \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \cdots + n(n-1)(n-2)(n-3)\cdots \big(n - (n-1) \big) + n(n-1)(n-2)(n-3)\cdots \big(n - (n-1) \big) m_{1} \\ &= n + n(n-1) + n(n-1)(n-2) + n(n-1)(n-2)(n-3) + \cdots + n(n-1)(n-2)(n-3)\cdots \big(n - (n-1) \big) \\ &= \frac{n!}{(n-1)!} + \frac{n!}{(n-2)!} + \frac{n!}{(n-3)!} + \cdots + \frac{n!}{1!} \\ &= \frac{n!}{1!} + \cdots + \frac{n!}{(n-1)!} \\ &= \sum_{k=1}^{n-1} \frac{n!}{k!}, \end{align} $$ as required.
Is this proof correct and clear enough? Or, are there any issues?