proof for Stirling numbers of the first kind

**Show that if p is an odd prime, then **$\displaystyle \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?

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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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?

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, $\displaystyle \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, $\displaystyle \begin{Bmatrix}p\\p-1\end{Bmatrix}$ is a multiple of p.