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