Tricks with factorials and binomials

Factorials and binomials show up a lot, but they are often pretty nasty to deal with. Here are a few tricks

Know some basic identities

Know that $n\log n \sim \log n!$, i.e. they are of the same complexity.

However, if you are taking the difference of facorials, this doesn’t get you as far

Take the log of both sides

This is often a good move because it turns products into summations

Use binomial identities

1. $\sum_k \binom{n}{k} = 2^n$

2. $\binom{n}{n/2} \geq \binom{n}{k}$ for all $k \leq n$

Split into factorials

remember that

From here you can combine factorials if needed. For example, $\binom{m+n}{n}$ can be simplified down to $\frac{(m+n)!}{m!n!}$

Turn it into product notation

Always remember that factorials have product notation associated with it.

The binomial coefficient has a nice rendering

Tricks with logs

The general rule is that $k^{\log_m(n)}$ can be expressed as $n^{\log_m(k)}$. This is because

In a pinch, just know that you can swap the base and the thing inside the log.

Here are some useful identities (some of these we derived before)

We also have some expansions and expansions to keep in mind

Floors and ceilings

These are provable facts