Chris Piech Handout #3
CS109 March 30, 2016
Calculation Reference
Handout written by Mehran Sahami
Useful identities related to summations
Since it may have been a while since some folks have worked with summations, I just
wanted to provide a reference on them that you may find useful in your future work.
Here are some useful identities and rules related to working with summations. In the
rules below, f and g are arbitrary real-valued functions.
Pulling a constant out of a summation:
, where C is a constant.
Eliminating the summation by summing over the elements:
, where C is a constant.
Combining related summations:
–2–
Changing the bounds on the summation:
"Reversing" the order of the summation:
Arithmetic series:
(with a moment of silence for C. F. Gauss.)
Arithmetic series involving higher order polynomials:
Geometric series:
–3–
More exotic geometric series:
Taylor expansion of exponential function:
Binomial coefficient:
Much more information on binomial coefficients is available in the Ross textbook.
Growth rates of summations
Besides solving a summation explicitly, it is also worthwhile to know some general
growth rates on sums, so you can (tightly) bound a sum if you are trying to prove
something in the big-Oh/Theta world. If you're not familiar with big-Theta (Θ) notation,
you can think of it like big-Oh notation, but it actually provides a "tight" bound. Namely,
big-Theta means that the function grows no more quickly and no more slowly than the
function specified, up to constant factors, so it's actually more informative than big-Oh.
Here are some useful bounds:
, for c ≥ 0.
, for c ≥ 2.
–4–
A few identities related to products
Recall that the mathematical symbol Π represents a product of terms (analogous to Σ
representing a sum of terms). Below, we give some useful identities related to products.
Definition of factorial:
n
∏i = n!
i =1
Note that 0! = 1 by definition.
Stirling's approximation for n! is given below. This approximation is useful when
computing n! for large values of n (particularly when n > 30).
n
⎛ n ⎞ ⎛ 1 ⎞
⎜ n+ ⎟
n! ≈ 2π n ⎜ ⎟ , or equivalently n! ≈ 2π n ⎝ 2 ⎠ −n
e
⎝ e ⎠
Eliminating the product by multiplying over the elements:
n
n
∏C = C
i =1
, where C is a constant.
Combining products:
n n n
∏ f (i) ⋅ ∏ g (i) = ∏ f (i) ⋅ g (i)
i =1 i =1 i =1
Turning products into summations (by taking logarithms, assuming f(i) > 0 for all i ):
⎛ n ⎞ n
log⎜⎜ ∏ f (i) ⎟⎟ = ∑ log f (i )
⎝ i =1 ⎠ i =1
–5–
Suggestions for computing permutations and combinations
For your problem set solutions it is fine for your answers to include factorials,
exponentials, or combinations; you don't need to calculate those all out to get a single
numeric answer. However, it you'd like to work with those in Microsoft Excel, here are a
few functions you may find useful:
In Microsoft Excel:
FACT(n) computes n!
⎛ n ⎞
COMBIN(n, m) computes ⎜⎜ ⎟⎟
⎝ m ⎠
EXP(n) computes en
POWER(n, m) computes nm
To use functions in Excel, you need to set a cell to equal a function value. For example,
⎛ 5 ⎞
to compute 3! * ⎜⎜ ⎟⎟ , you would put the following in a cell:
⎝ 2 ⎠
= FACT(3) * COMBIN(5, 2)
Note the equals sign (=) at the beginning of the expression.
–6–
A little review of calculus
Since it may have been a while since you did calculus, here are a few rules that you might
find useful.
Product Rule for derivatives:
d (u ⋅ v) = du ⋅ v + u ⋅ dv
Derivative of exponential function:
d (e u ) du
= eu
dx dx
Integral of exponential function:
u u
∫ e du = e
Derivative of natural logarithm:
d 1
ln( x) =
dx x
Integral of 1/x:
1
∫ x dx = ln( x)
Integration by parts: (everyone's favorite!)
Choose a suitable u and dv to decompose the integral of interest:
∫ u ⋅ dv = u ⋅ v − ∫ v ⋅ du
Here's the underlying rule that integration by parts is derived from:
∫ d (u ⋅ v) = u ⋅ v = ∫ v ⋅ du + ∫ u ⋅ dv
Bibliography
Additional information on sums and products can generally be found in a good calculus
or discrete mathematics book. The discussion of summations above is based on
Wikipedia. (http://en.wikipedia.org/wiki/Summation).
