Prove by double-counting: $\sum_{k=d} ^n {n \choose k} {k \choose d} = 2^ {(n-d)} {n \choose d} $?

Question

I'm thinking the left hand side is picking k people from n people and then picking d people from k people. For the right hand side, we have picking d people from n people first and this is where I'm stuck. I think I must explain $2^ {(n-d)}$ to be equal as picking k people from n people

Answer 1

Hint: Lets say that you have fence(wood sticks in a row) of length $n,$ you want to paint exactly $d$ of them blue. For painting them you have to put a white base first. The left hand side is first picking the $k$ ones you will paint white and from those the $d$ you are painting blue. The RHS is picking the blue first and then just choosing some $k$(you do not need to know exactly how many(can be any number $k$ between none and the remainder $n-d$)) for paint the remainder white.