Results 1 to 3 of 3

Math Help - proof for Stirling numbers of the first kind

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    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?
    Last edited by Yuuki; June 1st 2013 at 10:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2012
    From
    Normal, IL USA
    Posts
    149
    Thanks
    24

    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?
    Last edited by zhandele; June 2nd 2013 at 06:50 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating Function for Stirling Numbers (2nd kind)
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 18th 2012, 06:44 PM
  2. Replies: 2
    Last Post: November 4th 2010, 04:58 PM
  3. Stirling numbers of the second kind identity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 7th 2010, 06:46 PM
  4. Stirling numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 22nd 2010, 07:52 AM
  5. Stirling numbers
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 17th 2008, 07:43 PM

Search Tags


/mathhelpforum @mathhelpforum