<s>[INST] Proving a Binomial Identity 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)$.
Original Image
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.
 [/INST] 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.
</s>