Question

Can someone help me with a combinatorics problem?
I want to give a combinatorial proof, but I'm stuck from the beginning!

Answer 1

The problem is to prove the following.
\[\sum_{k=0}^{n}\left(\begin{matrix}n+k \\ k\end{matrix}\right)\left( \frac{ 1 }{ 2 } \right)^k=2^n\]

Answer 2

@welshfella

Answer 3

I proved it using mathematical induction, but can't think of any way to give a combinatorial proof("proof by counting")...

Answer 4

@mathstudent55