Math tips
Tags | CS161 |
---|
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 , 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
-
- for all
Split into factorials
remember that
From here you can combine factorials if needed. For example, can be simplified down to
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 can be expressed as . 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