<s>[INST] 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?
 [/INST] 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}$
</s>