# proof for Stirling numbers of the first kind

• Jun 1st 2013, 10:52 PM
Yuuki
proof for Stirling numbers of the first kind
Show that if p is an odd prime, then $\begin{Bmatrix}p\\ p-1\end{Bmatrix}$ is a multiple of p.

I tried to do this using recursion, but I failed to do so because I couldn't complete the
"if hypotheses is true for nth prime then it holds for the (n+1)th prime" step,
since I can't explicitly write down what the next prime is.
I tried to do a combinatorial approach of "distributing p distinct objects into p-1 identical classes", but I couldn't see the connection.
So I would like some hints.

How should I use p's prime-ness in my proof?
Also, is a combinatorial proof possible?
• Jun 2nd 2013, 06:38 PM
zhandele
Re: proof for Stirling numbers of the first kind
I haven't quite worked this out, but I can give you some hints.

First of all, I'm pretty sure you mean Stirling Numbers of the 2nd Kind, not the first. You're using the Knuth notation, where

$\left[\begin{matrix}p\\p-1\end{matrix}\right]$ stands for the Stirling Numbers first kind (I think it's pronounced "p bracket p-1") and

$\begin{Bmatrix}p\\p-1\end{Bmatrix}$ stands for the Stirling Numbers of the second kind ("p brace p-1.")

If you look at a table of Stirling Numbers (2nd kind), you'll see a diagonal of 1's. All numbers of the form

$\begin{Bmatrix}p\\p\end{Bmatrix}$ are equal to one. So the numbers you're interested in are in the "second diagonal" just below the first, that is, each one has a 1 above it in the table. Think of the recurrence relation. What does that mean?

Now consider the numbers in that second diagonal as a sequence. Construct a table of differences. What do you observe?
• Jun 2nd 2013, 08:26 PM
Yuuki
Re: proof for Stirling numbers of the first kind
Thank you, I was able to do the proof.

From the recurrence, [tex]\begin{Bmatrix}n\\n-1\end{Bmatrix}=\sum_{k=1}^{n-1}k[tex] in general.
In particular, $\begin{Bmatrix}p\\p-1\end{Bmatrix}=\sum_{k=1}^{p-1}k=\frac{1}{2}p(p-1)$.
Since p is odd, p-1 is even and (p-1)/2 is an integer.
Hence, $\begin{Bmatrix}p\\p-1\end{Bmatrix}$ is a multiple of p.