Background

When doing asymptotic analysis, it is useful to know certain identities. This page collects some of the useful ones.

Exponentials and Logarithms

Logarithms and exponentiation will be encountered frequently in this course. Below are some useful identities: \[\log_a{b} =\frac{\log_c{b}}{\log_c{a}}\text{ for any }a,b,c>0.\] \[a^b\cdot a^c = a^{b+c}\text{ for any }a,b,c.\]

Sums

Below are some sums that are useful to know:

• \[\sum_{i=1}^n i =\binom{n+1}{2}=\frac{n(n+1)}{2}.\] For an example analysis where the above identity is useful (as well as its proof), see the page on induction.

• \[\sum_{i=0}^{\infty} \frac{1}{2^i} = 2.\] The proof of this follows from known formula for sum of geometric series. See the Wikipedia page on geometric series for more.