Combinatorial proof of $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$ 
Give a combinatorial proof for this identity for non-negative integer $k$ and $n$ such that $0 \leq k < n$
$$\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$$

My attempt: I tried to reduce this identity.
Since $k,n$ are nonnegative integer and $k<n$ then I can change the upper limit into
$$\sum_{j=0}^{n-1} \binom{n}{j} =2^n-1 \quad \text{and} \quad \sum_{j=0}^{n-1} \binom{n-1-j}{n-1-j}2^j = \sum_{j=0}^{n-1} 2^j ~.$$
So, I just need to show $$\sum_{j=0}^{n-1} 2^j =2^n-1 $$ using combinatorial proof.
Am I right? I really need helps
 A: Big hint 
$\sum_{j=0}^k\binom{n}j$ counts subsets of $\{1,2,\dots,n\}$ with at most $k$ elements. Such a subset is missing at least $n-k$ elements. Arrange the missing elements in a sorted list, so the first element in the list is the smallest missing element. For how many such subsets is the $(n-k)^{th}$ entry of the list of missing elements equal to $n-j$?
Further explanation, just shy of a full solution:

If a subset satisfies this condition, then the element $n-j$ is missing, and among the elements $\{1,2,\dots,n-j-1\}$, exactly $n-k-1$ are missing. The elements above $n-j$ are either included or excluded, arbitrarily. 

Here is an illustration for $n=5,k=3$. We represent subsets as a string of zeroes and ones. The $(n-k)^{th}$ smallest, i.e. second smallest, missing element is highlighted in red. 
$$
\begin{array}{c|c|c|c}
\binom{5-1-0}{3-0} & \binom{5-1-1}{3-1}2 & \binom{5-1-2}{3-2}2^2 & \binom{5-1-3}{3-3}2^3
\\\hline
1110\color{red}0 & 110\color{red}00 &10\color{red}000 &0\color{red}0000
\\
1101\color{red}0 & 110\color{red}01 &10\color{red}001&0\color{red}0001
\\
1011\color{red}0 & 101\color{red}00 &10\color{red}010&0\color{red}0010
\\
0111\color{red}0 & 101\color{red}01 &10\color{red}011&0\color{red}0011
\\
 &  011\color{red}00 &01\color{red}000&0\color{red}0100
\\
 &  011\color{red}01&01\color{red}001&0\color{red}0101
\\
 & &01\color{red}010&0\color{red}0110
\\
& &01\color{red}011&0\color{red}0111
\end{array}
$$
