Evaluating Sums Algebraically or Combinatorially Consider
(1) $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}$$
(2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$
These sums appear too difficult (in my mind) to evaluate combinatorially.  What are some good methods to attack these problems algebraically?
 A: A combinatorial argument for (1) isn’t too hard. First rewrite the sum:
$$\sum_k\binom{n}k2^{k-n}=2^{-n}\sum_k\binom{n}k2^k\;.$$
Now $\binom{n}k2^k$ is the number of ways of choosing a $k$-subset $S$ of $[n]$ and then a subset $T$ of $S$, so $\sum_k\binom{n}k2^k$ is the number of ways of splitting $[n]$ into three subsets. This is clearly $3^n$, so the original expression is $\left(\frac32\right)^n$.
I don’t at the moment see a useful combinatorial interpretation of the second summation, but I can evaluate it. If
$$f(n)=\sum_{k=0}^n\binom{n}k\frac{k!}{(n+k+1)!}\;,$$
then we have the following data:
$$\begin{array}{c|r}
n&f(n)\\ \hline
0&1=\frac{2^0}{1!!}\\
1&\frac12+\frac16=\frac23=\frac{2^1}{3!!}\\
2&\frac16+\frac2{24}+\frac2{120}=\frac4{15}=\frac{2^2}{5!!}\\
3&\frac1{24}+\frac1{40}+\frac1{120}+\frac1{840}=\frac8{105}=\frac{2^3}{7!!}\\
4&\frac1{120}+\frac1{180}+\frac1{420}+\frac1{1680}+\frac1{15120}=\frac{16}{945}=\frac{2^4}{9!!}
\end{array}$$
Apparently $f(n)=\dfrac{2^n}{(2n+1)!!}=\dfrac{4^nn!}{(2n+1)!}$. Now
$$\begin{align*}
\frac{(2n+1)!}{n!}f(n)&=\frac{(2n+1)!}{n!}\sum_{k=0}^n\binom{n}k\frac{k!}{(n+k+1)!}\\\\
&=\frac1{n!}\sum_{k=0}^n\binom{n}kk!(2n+1)^{\underline{n-k}}\\\\
&=\frac1{n!}\sum_{k=0}^nn^\underline k(2n+1)^{\underline{n-k}}\\\\
&=\sum_{k=0}^n\frac{(2n+1)^{\underline{n-k}}}{(n-k)!}\\\\
&=\sum_{k=0}^n\frac{(2n+1)!}{(n-k)!(n+k+1)!}\\\\
&=\sum_{k=0}^n\binom{2n+1}{n-k}\\\\
&=\sum_{k=0}^n\binom{2n+1}k\;.
\end{align*}$$
(Here $x^{\underline k}$ is the falling factorial.) And
$$\sum_{k=0}^n\binom{2n+1}k=\sum_{k=0}^n\binom{2n+1}{2n+1-k}=\sum_{k=n+1}^{2n+1}\binom{2n+1}k\;,$$
so
$$\frac{(2n+1)!}{n!}f(n)=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k=2^{2n}=4^n\;,$$
and the conjecture that $f(n)=\dfrac{2^n}{(2n+1)!!}=\dfrac{4^nn!}{(2n+1)!}$ is established.
A: The second sum
$$ \sum_{k=0}^{n} \binom{n}{k} \frac{k!}{(n+k+1)!} $$
can be rewritten as
$$\frac{n!}{(2n+1)!} \sum_{k=0}^{n} \binom{2n+1}{n-k} = \frac{2^{2n} n!}{(2n+1)!}$$
expand $\binom{n}{k} = \frac{n!}{(n-k)!k!}$, cancel the $k!$ and multiply and divide by $(2n+1)!$ and,
$\sum_{k=0}^{n} \binom{2n+1}{n-k} = \binom{2n+1}{n} + \binom{2n+1}{n-1} + \dots + \binom{2n+1}{0} =  \frac{1}{2} \sum_{k=0}^{2n+1} \binom{2n+1}{k} = 2^{2n}$
A: $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}=2^{-n}\sum_{k=0}^{n}\binom{n}{k}2^k\cdot1^{n-k}=2^{-n}(2+1)^n=(3/2)^n$$
A: For $(1)$, consider the binomial theorem. First write $2^{k-n}$ as $\left(\frac{1}{2}\right)^{n-k}$. Then:
$$\sum_{k=0}^{n} {n \choose k} 2^{k-n} = \sum_{k=0}^{n} {n \choose k} \left(\frac{1}{2}\right)^{n-k} 1^{k} = \left(1+\frac{1}{2}\right)^{n}=\left(\frac{3}{2}\right)^{n}$$   
Numerical results suggest that the second sum can be written as $$\sum_{k=0}^{n} {n \choose k}\frac{k!}{(n+k+1)!}=\frac{2^{n}}{1*3*\ldots*(2n+1)}=\frac{n!}{(2n+1)!}$$   
