2
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

$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.

$\endgroup$
7
  • $\begingroup$ Could you clarify what you mean by identity(2)? $\endgroup$
    – D idsea J
    Jan 17, 2019 at 15:24
  • 1
    $\begingroup$ $s_{n,n-1} = \frac{n(n-1)}{2} \tag 2$.. This is what I mean. $\endgroup$ Jan 17, 2019 at 15:26
  • $\begingroup$ Alright, even though I thought the final form after induction should be $\frac{1}{24}(n+1)(n)(n-1)(3n)$ cause that's what we get if we put n=n+1 into the formula that we need to proof. $\endgroup$
    – D idsea J
    Jan 17, 2019 at 15:32
  • $\begingroup$ It might be a stupid question. However, when doing induction last time it was always the case that you could just put n+1 into the formula you have to proof to see what the end should look like. I don't see why this is a proof if it's not the same in the end to be honest. $\endgroup$
    – D idsea J
    Jan 17, 2019 at 15:43
  • $\begingroup$ Wolfram states, that the special case for stirling first kind s(n,n-1) is -(n choose 2). So who's right now o_O $\endgroup$
    – D idsea J
    Jan 18, 2019 at 8:05
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .