Combinatorial argument

In discrete mathematics, a combinatorial argument is an argument based on counting. The core idea is that we want to show a certain combinatoric expression accurately describes the question. The method is as follows:

• Question: ask a question relating to the formula you’d like to prove. Sometimes this is given to us, sometimes we have to formulate this from scratch.
• LHS: argue why the LHS answers the question.
• RHS: argue why the RHS answers the question.

We can choose the easier side to start. This can usually be done definitionally:

• Thinking about choosing $k$ objects from a set of $n$ (without replacement) $\to {}^n{C}_k$.
• Or by forming $n$-letter strings from an alphabet of size $k$ (selection with replacement) $\to k^n$.

One critical thing to remember is that the argument isn’t supposed to be based on equations or proofs. We should be able to express the argument in plain English.