Prove the following by using a proof by industion:
$$\sum\limits_{k=0}^{n} |s(n,k)| = n!$$
where $s(n,k)$ is the Stirling Numbers of the First Kind.
Workings:
Proof:
The recurrence relation for $s(n,k)$ would be:
$s(n+1,k)=s(n,k-1)-ns(n,k)$
Base case: $n = 0$
So $S(0,0) = 1 = 0!$
Base case holds.
Induction hypothesis:
Suppose that $\sum\limits_{k=0}^{n} |s(n,k)| = n!$ holds for some n.
Then for $n+1$
$\sum\limits_{k=0}^{n+1} |s(n,k)| = \sum\limits_{k=0}^{n} |s(n,k)| + |s(n+1,k)|$
= $n! + |s(n+1,k)|$
I'm not sure if what I said so far is correct and what to do next.
Any help will be appreciated.
You got a bit mixed up with your indexing.
Suppose that $\sum_{k=0}^n |s(n,k)|=n!$ holds for some n. This is fine.
Then for $n+1$, you need to start with
$$ \sum_{k=0}^{n+1} |s(n+1,k)| = \sum_{k=0}^{n+1} |s(n,k-1) - ns(n,k)| = \cdots$$
See if you can take it from there. You want to show that this is equal to $(n+1)!$.