# Thread: Proving an identity with unsigned sterling numbers of first kind

1. ## Proving an identity with unsigned sterling numbers of first kind

How do I prove $\displaystyle c(n+1, m+1) = \sum_{k=0}^{n} c(n, k) \binom{k}{m}$

2. ## Re: Proving an identity with unsigned sterling numbers of first kind

have you tried induction?

3. ## Re: Proving an identity with unsigned sterling numbers of first kind

The base case is easy to show, but for the induction step do I assume $\displaystyle c(n, m+1) = \sum_{k=0}^{n-1} c(n-1, k) \binom{k}{m}$ is true? and then try to get to $\displaystyle c(n+1, m+1) = \sum_{k=0}^{n} c(n, k) \binom{k}{m}$?

Edit: I am assuming that we want to induct on n.

4. ## Re: Proving an identity with unsigned sterling numbers of first kind

Originally Posted by evg952
The base case is easy to show, but for the induction step do I assume $\displaystyle c(n, m+1) = \sum_{k=0}^{n-1} c(n-1, k) \binom{k}{m}$ is true? and then try to get to $\displaystyle c(n+1, m+1) = \sum_{k=0}^{n} c(n, k) \binom{k}{m}$?

Edit: I am assuming that we want to induct on n.
err what's the difference between $c(m,n)$ and $\begin{pmatrix}m \\n\end{pmatrix}$ ?