0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What are the $b_n$? $\endgroup$ – Umberto P. Jan 28 '15 at 16:17
  • $\begingroup$ @UmbertoP. The Bell numbers according to my prof. $\endgroup$ – TillermansTea Jan 28 '15 at 16:46
  • $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Jan 28 '15 at 18:19
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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}.$ $\endgroup$ – TillermansTea Jan 28 '15 at 16:15
  • 1
    $\begingroup$ The answer shows that the stated recurrence, along with $b_0 = 1$, is the same as the Bell recurrence. $\endgroup$ – Umberto P. Jan 28 '15 at 16:50
  • $\begingroup$ Isn't that just the definition? What is there to prove? $\endgroup$ – miniparser Jan 28 '15 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.