I have found this formula which is a combinatorial identity for counting binary words. I'd like more information on it, or the name of the proof. I am also not totally clear on the step between the identity and the equivalent identity. Any ideas?
The formula:
$$\sum_{k = 0}^{n}\binom{n + k}{n}2^{-k} = 2^{n}$$
The proof is a counting proof using this equivalent identity:
$$\sum_{k = 0}^{n}\binom{n + k}{n}2 \cdot 2^{n-k} = 2^{2n + 1}$$
EDIT: I found the source in Pearls of Discrete Mathematics, example 3.4 here