proof for Stirling numbers of the first kind

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

stands for the Stirling Numbers first kind (I think it's pronounced "p bracket p-1") and

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

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

Since p is odd, p-1 is even and (p-1)/2 is an integer.

Hence, is a multiple of p.