Problem $\boldsymbol{25}$ [$\boldsymbol{5}$ Points]: Show that $$ \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}=2^n $$ Hint: Denote the left hand side by $f(n)$ and prove that $f(n+1)=2f(n)$.
Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem and using different summation identities but i just cant get there. Please help me.
Showing the hint is just a straightforward calculation. If $f(n) = \sum \binom{n+k}{k} \frac{1}{2^k}$, then \begin{align*} f(n+1) &= \sum_{k=0}^{n+1} \binom{n+k+1}{k} \frac{1}{2^k} \\ &= \sum_{k=1}^{n+1} \binom{n+k}{k-1} \frac{1}{2^k} + \sum_{k=0}^{n+1} \binom{n+k}{k} \frac{1}{2^k} \\ &= \frac{1}{2} \sum_{k=0}^n \binom{n+k+1}{k} \frac{1}{2^k} + \sum_{k=0}^{n+1} \binom{n+k}{k} \frac{1}{2^k} \\ &= \frac{1}{2}\left[ \sum_{k=0}^{n+1} \binom{n+k+1}{k} \frac{1}{2^k} - \binom{2n+2}{n+1}\frac{1}{2^{n+1}}\right] \\ &\quad + \left[ \sum_{k=0}^{n} \binom{n+k}{k} \frac{1}{2^k} + \binom{2n+1}{n+1} \frac{1}{2^{n+1}} \right] \\ &= \frac{1}{2} f(n+1) + f(n) + \frac{1}{2^{n+2}} \left[ 2\binom{2n+1}{n+1} - \binom{2n+2}{n+1} \right] \\ &= \frac{1}{2} f(n+1) + f(n), \end{align*} and so $f(n+1) = 2f(n)$. Now, showing the result follows by induction.