Induction proof for stirling of first kind.

245 Views Asked by At

I have to show that for every stirling number of the first kind $\forall n \geq 2 : s_{n,n-2} = \frac{1}{24}n(n-1)(n-2)(3n-1) $ is true.

I've started like this:

Base case: Let $n$ be $n=2$, then per defintion $s_{n,0} = 0$. Since we have $s_{2,2-2} = s_{2,0} = 0$ and $\frac{1}{24}2(2-1)(2-2)(3*2-1) = \frac{1}{24}2(2-1)(0)(3*2-1) = 0$ the base case is true.

Now we assume $\forall n \in \mathbb{N} $ with $ n \geq 2$ that $s_{n,n-2} = \frac{1}{24}n(n-1)(n-2)(3n-1) $ is true.

We also now, that there exists a recursive formula for the stirling numbers of the first kind which will help us for the induction.

It says that $s_{n,k} = s_{n-1,k-1}+(n-1)s_{n-1,k} $.

Now let $n \rightarrow n+1$.

$s_{n+1,n-1} = s_{n,n-2}+n*s_{n,n-1} $.

If we insert our assumption, that leaves us with

$s_{n+1,n-1} = \frac{1}{24}n(n-1)(n-2)(3n-1)+n*s_{n,n-1} $.

If we insert $n=n+1$ into $\frac{1}{24}n(n-1)(n-2)(3n-1)$ we get $\frac{1}{24}n+1(n)(n-1)(3n)$, so that's what we would like after the induction.

The big problem now is that I can'T get rid of $s_{n,n-1}$. I've seen a similar question for the stirling numbers of second kind which simply say that $S_{n,n-1} = $$n \choose 2$ but I don't know if this is true for the first kind and neither did I understand how we come to that conclusion. Can anyone help me?

2

There are 2 best solutions below

7
On BEST ANSWER

$s_{n+1,n-1} = \frac{1}{24}n(n-1)(n-2)(3n-1)+n*s_{n,n-1} \tag1$.

$s_{n,n-1} = \frac{n(n-1)}{2} \tag 2$.

Substitute this in the prior equation we get

$s_{n+1,n-1} = \frac{1}{24}n(n-1)(n-2)(3n-1)+\frac{n^2(n-1)}{2} $.

which simplifies to

$s_{n+1,n-1} = \frac{1}{24}(n+1)n(n-1)(3n+2)\tag 3 $.

Thus proved by induction. You will have to use the identity(2) to get the final proof. I don't think there is any way out.

0
On

Induction step:

$\begin{aligned}s\left(n+1,n-1\right) & =ns\left(n,n-1\right)+s\left(n,n-2\right)\\ & =\frac{1}{2}n^{2}\left(n-1\right)+\frac{1}{24}n\left(n-1\right)\left(n-2\right)\left(3n-1\right)\\ & =\frac{1}{24}n\left(n-1\right)\left[12n+\left(n-2\right)\left(3n-1\right)\right]\\ & =\frac{1}{24}n\left(n-1\right)\left(n+1\right)\left(3n+2\right)\\ & =\frac{1}{24}\left(n+1\right)n\left(n-1\right)\left(3n+2\right) \end{aligned} $

In the second equality we use the equality $s(n,n-1)=\frac12n(n-1)$ and also the induction hypothesis.