prove for bell number using induction on n

Question

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

Answer 1

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*}