# Combinatorial Proof of Identity b_n

Prove that:

$$b_n = 1 + \sum\limits_{k=1}^{∞} \binom{n-1}{k}b_k.$$

Workings:

The first thing I noticed is that the above equation looks very similar to a Bell Numbers proof:

$b_{n+1}=\sum\limits_{k=0}^n\binom{n}{k}b_k$

Making me think there is some sort of relation between the two. Though this may not be true. Since the one I need to prove does have an infinity.

So because of this I'm not to sure on what to do.

Any help will be appreciated.

• What are the $b_n$? – Umberto P. Jan 28 '15 at 16:17
• @UmbertoP. The Bell numbers according to my prof. – TillermansTea Jan 28 '15 at 16:46
• The upper limit of $\infty$ doesn’t matter: $\binom{n-1}k$ is non-zero only for $0\le k\le n-1$ anyway, so in effect the summation is from $1$ through $n-1$. – Brian M. Scott Jan 28 '15 at 18:19

If $k > n-1$ then $\binom{n-1}{k} = 0$. Thus the original equality states $$b_n = 1 + \sum_{k=1}^{n-1} \binom{n-1}{k} b_k.$$ If you have that $b_0 = 1$ then $1 = \binom{n-1}{0} b_0$ so in fact $$b_n = \sum_{k=0}^{n-1} \binom{n-1}{k} b_k.$$
• So for a proof I could: suppose we are partitioning the set {1,2,…,n}. Focus first on the block containing the element 1. Let k denote the number of elements other than 1 that belong to this block. We can choose these elements in $\binom{n-1}{k}$ ways. Having formed this block, we partition the remaining $n−k$ elements in $b_{n−k}$ ways. Summing over $k$ gives: $\sum_{k = 0}^{n-1} \binom{n-1}{k} b_{n-k}.$ ways Which is equivalent to $\sum_{k = 0}^{n-1} \binom{n-1}{k} b_{k}.$ – TillermansTea Jan 28 '15 at 16:15
• The answer shows that the stated recurrence, along with $b_0 = 1$, is the same as the Bell recurrence. – Umberto P. Jan 28 '15 at 16:50