write the most simple algebraic proof you can, that means no integrals and no exponential generating functions if possible. I have tried to solve it for close to 2 hours. what I got to is almost nothing but here it is : $1/2 * \mathrm{2}^{2n+1}=\mathrm{2}^{2n}=\mathrm{4}^n=\mathrm{(2+2)}^n= \sum_{k=0}^n\binom{n}{k}\mathrm{2}^k\mathrm{2}^{n-k}=?\sum_{k=0}^n {n+k \choose n}\mathrm{2}^{n-k} $ and that's it. this is the first time I tried to use symbols so if something goes wrong, I am terribly sorry.
Hint:
You could try it as follows
The given expression can be written as $$2^n \sum_{k=0}^n \binom {n+k}{n}\cdot 2^{-k}$$
This can also be written as $$2^n \cdot \text {coefficient of $x^n$ in the expansion } \left[\left( \frac {1}{2}+x\right)^n +\left( \frac {1}{2}+x\right)^{n+1}+ \cdots +\left( \frac {1}{2}+x\right)^{2n}\right]$$
We can also add the remaining terms of the series inside the bracket because nevertheless they are not going to give the coefficient of $x^n$ in their expansion.
Hence we need to find $$2^n \cdot \text {coefficient of $x^n$ in the expansion } \left[\left( \frac {1}{2}+x\right)^0 +\left( \frac {1}{2}+x\right)^{1}+ \cdots +\left( \frac {1}{2}+x\right)^{2n}\right]$$
Now whatever inside the square bracket is nothing but a Geometric progression written out there which can be easily summed.
I hope you can take it from here.