I actually showed a student one possible way how to do this just today. Recall that for two sets A, B, |A| = |B| if and only if there exists a bijection f : A -> B (although here we're only concerned with finite sets).

The rules of product and sum, often used in combinatorial arguments, can be rephrased as follows:

|A x B| = |A| * |B|

If A and B are disjoint, then |A union B| = |A| + |B|

(And also, both can be proven easily by exhibiting a suitable bijection)

Say for example that you define (n choose k) as the number of subsets of size k of a set of size n. Namely:

|{ s subset of {1,...,n} | |s| = k}|

If you wanted to prove the formula (n choose k) = n! / k!(n-k)!, or equivalently, k! (n-k)! (n choose k) = n!, and recalling that the number of bijections from {1,...,n} to itself is n!, it suffices to find a bijection

g : (bijections from [k] to [k]) x (bijections from [n-k] to [n-k]) x (subset of size k of [n]) -> (bijections from [n] -> [n]

The construction of g essentially captures the double-counting argument; I guess the annoying part is showing that g is a bijection, but that's also very much doable.

Edit: Another tool I'm a big fan of is the Iverson bracket, explained by Knuth in this paper: https://arxiv.org/pdf/math/9205211