# prove for bell number using induction on n [duplicate]

hi guys I have to prove this equality $$B_n=e^{-1}\sum_{k=0}^{\infty}\frac{k^n}{k!},$$ that is called bell equality only using induction on $$n$$ . How can i do this? I have tried by substituting the recursive formula $$\sum\limits_{k=0}^{n} \binom{n}{k} B_{k}$$ in the first one. But I am completely lost with indexes. I have already tried to search some informations on the internet but nothing using induction

• I´ve made an edit. Please check if it is what you meant. Mar 3 at 8:14
• Also, relevant: en.wikipedia.org/wiki/… (Dobinski's formula). Mar 3 at 8:15
• yes thank you is perfect Mar 3 at 8:15
• Something like this? math.stackexchange.com/questions/1829448/… Mar 3 at 8:16
• @ClementC. it is similar but i don't know what happened when the guy that posted the question from the 2 sums obtained only 1 and why called the 2 sums with different indeces Mar 3 at 9:07

Using the Bell´s formula we have that $$B(n)=\sum\limits_{k=0}^nS(n,k).$$ This is the total number of ways to put $$n$$ balls in an arbitrary number of boxes (no empty boxes remaining). To count them we look at the number of balls (at this parameter we will call it $$a$$, and it can be from $$0$$ to $$(n - 1)$$) that accompany any ball (for example ball number $$1$$) on your box. To do this:

• First we choose the $$a$$ companions of ball $$1$$ from among the $$(n - 1)$$ possible (which can be done in $$\binom{n-1}{a}$$ different ways).
• Then, for each way of selecting the companions, we count how many ways they can be entered the remaining $$(n − 1 − a)$$ balls in an arbitrary number of boxes (we have called this $$B(n−1−a)$$)

$$\boxed{B(n)}=\sum\limits_{a=0}^{n-1}{\dbinom{n-1}{a}}\sum\limits_{k=1}^{n-1-a}{S(n-1-a)}=\boxed{\sum\limits_{a=0}^{n-1}{\dbinom{n-1}{a}B(n-1-a)}}$$

Now, if we define the $$DOB$$ function this way: $$DOB(n)=\sum\limits_{k=1}^{\infty}\dfrac{k^n}{n!},$$ we can see that

\begin{align*} DOB(0)&=1+\dfrac{1}{1!}+\dfrac{1}{2!}+\dfrac{1}{3!}+\dfrac{1}{4!}+\cdots\\ DOB(1)&=\phantom{OO}\dfrac{1}{1!}+\dfrac{2}{2!}+\dfrac{3}{3!}+\dfrac{4}{4!}+\cdots\\ DOB(2)&=\phantom{OO}\dfrac{1^2}{1!}+\dfrac{2^2}{2!}+\dfrac{3^2}{3!}+\dfrac{4^2}{4!}+\cdots\\ DOB(3)&=\phantom{OO}\dfrac{1^3}{1!}+\dfrac{2^3}{2!}+\dfrac{3^3}{3!}+\dfrac{4^3}{4!}+\cdots \end{align*}

By combining these numbers we get that

$$\begin{gather*} \color{red}{1}DOB(0)+\color{red}{2}DOB(1)+\color{red}{1}DOB(2)=1+\dfrac{4}{1!}+\dfrac{9}{2!}+\dfrac{27}{3!}\cdots=\dfrac{1^3}{1!}+\dfrac{2^3}{2!}+\dfrac{3^3}{3!}+\dfrac{4^3}{4!}+\cdots=DOB(3)\\ \color{red}{1}DOB(0)+\color{red}{3}DOB(1)+\color{red}{3}DOB(2)+\color{red}{1}DOB(3)=1+\dfrac{8}{1!}+\dfrac{27}{2!}+\dfrac{64}{3!}\cdots=\dfrac{1^4}{1!}+\dfrac{2^4}{2!}+\dfrac{3^4}{3!}+\dfrac{4^4}{4!}+\cdots=DOB(4) \end{gather*}$$

What Dobinsky wanted to prove is that both sequences fulfill the same recurrence, and that have the following property:

$$DOB(n)=\sum\limits_{j=0}^{n-1}{\dbinom{n-1}{j}DOB}(j)$$

To prove this just use the binomial Theorem:

\begin{align*} \boxed{\sum\limits_{j=0}^{n-1}{\dbinom{n-1}{j}DOB(j)}}=&\ e+\sum\limits_{j=1}^{n-1}{\dbinom{n-1}{j}DOB(j)}=e+\sum\limits_{j=1}^{n-1}{\dbinom{n-1}{j}\sum\limits_{k=1}^{\infty}{\dfrac{k^n}{n!}}}\\ =&\ e+\sum\limits_{k=1}^{\infty}{\dfrac{1}{k!}}\underbrace{\sum\limits_{j=1}^{n-1}{\dbinom{n-1}{j}k^j}}_{=(k+1)^{n-1}-1}=\ e-\underbrace{\sum\limits_{k=1}^{\infty}{\dfrac{1}{k!}}}_{=e-1}+\sum\limits_{k=1}^{\infty}{\dfrac{(k+1)^{n-1}}{k}}\\ =&1+\sum\limits_{k=1}^{\infty}{\dfrac{(k+1)^{n-1}}{k!}=1+\sum\limits_{k=1}^{\infty}{\dfrac{(k+1)^n}{(k+1)!}}=\sum\limits_{k=1}^{\infty}{\dfrac{j^n}{j!}}}=\boxed{DOB(j)} \end{align*}

This tells us that: $$\begin{equation}\label{Formula_Dobinsky} eB(n)=DOB(n) \rightarrow \boxed{B(n)=\dfrac{1}{e}\sum\limits_{k=1}^{\infty}{\dfrac{k^n}{k!}}}\quad \text{for each }n=1,2,3\ldots \end{equation}$$

This formula is way more friendly and computerwise more stable. To see that just check that

$$\begin{equation*} B(10)=115975;\qquad\dfrac{1}{e}\sum\limits_{k=1}^{15}{\dfrac{k^{10}}{k!}}=115974.978 \end{equation*}$$