How to prove the following identity: $\sum_{l = 0}^k \frac{1}{(l+1)!(k-l)!} = \sum_{l = 0}^k \frac{2^{k-l}}{(k+1)!}$ More broadly; I will need to prove
$\sum_{k_{n-1} = 0}^{k_n}...\sum_{k_2 = 0}^{k_3}\sum_{k_1 = 0}^{k_2} \frac{1}{(k_1+1)!(k_2-k_1)!(k_3-k_2)!...(k_n-k_{n-1})!} = \sum_{k_{n-1} = 0}^{k_n}...\sum_{k_2 = 0}^{k_3}\sum_{k_1 = 0}^{k_2} \frac{(n-1)!2^{k_2-k_1} 3^{k_3-k_2} 4^{k_4-k_3}...}{(k_n+1)!}$
I'm guessing similar arguments will apply for that more general case, but some intuition for either would be greatly appreciated!
Thank you
 A: Case $n=2$. We have that
$$\sum_{k_1 = 0}^{k_2} \frac{1}{(k_1+1)!(k_2-k_1)!}=\frac{1}{(k_2+1)!}\sum_{k_1 = 0}^{k_2} \binom{k_2+1}{k_1+1}=\frac{2^{k_2+1}-1}{(k_2+1)!}=\sum_{k_1 = 0}^{k_2} \frac{2^{k_2-k_1}}{(k_2+1)!}.$$
Can you prove the general case?
A: Here's a non-induction based proof of the equality stated in the title
$$\sum\limits_{k=0}^n\frac 1{(k+1)!(n-k)!}=\sum\limits_{k=0}^n\frac {2^{n-k}}{(n+1)!}$$
Take the left-hand side and multiply the numerator and denominator by $(n+1)!$. This allows the sum to be rewritten in terms of the binomial coefficient
$$\sum\limits_{k=0}^n\color{red}{\frac {(n+1)!}{(k+1)!(n-k)!}}\frac 1{(n+1)!}=\sum\limits_{k=0}^n\color{red}{\binom {n+1}{k+1}}\frac 1{(n+1)!}$$
Next, recall the Hockey-stick identity
$$\sum\limits_{j=0}^n\binom jk=\binom {n+1}{k+1}$$
Substituting for the red part of the expression gives us a double sum
$$\sum\limits_{k=0}^n\binom {n+1}{k+1}\frac 1{(n+1)!}=\frac 1{(n+1)!}\sum\limits_{k=0}^n\sum\limits_{j=0}^n\binom jk$$
By expanding the double sum into its constituents, we can rewrite our nested sum by using the fact that
$$\binom nk=0\qquad\qquad n<k$$
Our double sum is equal to
$$\begin{array}{cccccccccc}\left[\dbinom 00\right. & + & \dbinom 10 & + & \dbinom 20 & + & \cdots & + & \left.\dbinom n0\right] & +\\\left[\phantom{\dbinom 00}\right. & & \dbinom 11 & + & \dbinom 21 & + & \cdots & + & \left.\dbinom n1\right] & +\\\left[\phantom{\dbinom 00}\right. & & & & \dbinom 22 & + & \cdots & + & \left.\dbinom n2\right] & +\\ & & & & \vdots\\\left[\phantom{\dbinom 00}\right. & & & & & & & & \left.\dbinom nn\right] & +\end{array}$$
For any column $k$ starting from right to left, we have the sum of binomials down the column as
$$\sum\limits_{j=0}^{n-k}\binom {n-k}j=2^{n-k}$$
Where the right-hand side comes naturally from the binomial theorem. Seeing that our $k$ must be $0\leq k\leq n$, our expression can be simplified into
$$\sum\limits_{k=0}^n\sum\limits_{j=0}^n\binom jk=\sum\limits_{k=0}^n\sum\limits_{j=0}^{n-k}\binom {n-k}j=\sum\limits_{k=0}^n2^{n-k}$$
Moving the $(n+1)!$ term into our sum, we prove the identity stated in the title.
$$\sum\limits_{k=0}^n\frac 1{(k+1)!(n-k)!}\color{blue}{=\sum\limits_{k=0}^n\frac {2^{n-k}}{(n+1)!}}$$
A: The top equality can be easily proved by induction. Since $\sum_{l=0}^{k+1}\frac{1}{(l+1)!(k+1-l)!}=\sum_{l=0}^{k}\frac{1}{(l+1)!(k-l)!}+\frac{1}{(k+2)!0!}$ and $\sum_{l=0}^{k+1}\frac{2^{k+1-l}}{(k+2)!} =\sum_{l=0}^{k}\frac{2^{k-l}}{(k+1)!}+\frac{2^{k+1-k-1}}{(k+2)!}$. The k+1 term is the same in both sums , therefore it is true for all  $ k\in \mathbb{N}$. I believe that the more general case can also be proved by induction on $k_{1},k_{2},..,k_{n}$ but the presentation is a lot more complicated!
