Recall that a combinatorial proof for an identity proceeds as

follows

1. State a counting question.

2. Answer the question in two ways:

(i) one answer must correspond to the left-hand side (LHS)

of the identity

(ii) the other answer must correspond to the right-hand