Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. High and mighty

An integer n is high if n >= 1 and, for any m < n, if m is high then n >= 2m.

An integer n is mighty if n >= 1 and n is strictly greater than the sum of all smaller mighty integers.

Show that an integer is high if and only if it is mighty.

1.1. Solution

We'll show that the high and mighty integers are both the set { 2^x | x in N }.

Lemma: n is high iff it is of the form 2^x.
Proof: By induction on n. Observe that 1 = 2⁰ is high, since there is no m < n that is high and thus it is vacuously at least twice all such m. Now consider some n > 1. If n = 2^k for some k, by the induction hypothesis the largest high m < n is 2^k-1; so we have n = 2^k >= 2*2^k-1 >= 2m for all high m < n and n is high. If n is not a power of 2, it must lie between 2^k and 2^k+1 for some k, and by the induction hypothesis 2^k is high. But then n < 2*2^k and n is not high.
Lemma: n is mighty iff it is of the form 2^x.
Proof: Again by induction on n. The base case is n=1; since there no smaller mighty integers, 1 trivially exceeds their sum and is mighty. For larger n, if n=2^k then the induction hypothesis gives that the set of smaller mighty integers is 1, 2, 4, ... 2^{k-1$, and the sum of these integers is 2}k^{-1 by the geometric series formula. Since n > 2}k^{-1, n is mighty. Alternatively, if n is not a power of 2, let 2}k^{be the largest power of 2 less than n. Again we have 1, 2, 4, ..., 2}k^{are all mighty, and their sum is 2}k+1^-1 >= n. Thus n is not mighty.

We have thus shown than n is high iff n = 2^k iff n is mighty.

2. Injections, surjections, and compositions

Prove or disprove: fg is injective if and only if both f and g are injective.
Prove or disprove: fg is surjective if and only if both f and g are surjective.

2.1. Solution

Disproof: We'll construct f and g such that f is not injective but fg is. Let g:{0}->{0,1} be given by g(0) = 0, and let f:{0,1}->{0} be given by f(0) = f(1) = 0. Then f is not injective, but fg:{0}->{0} is the identity function fg(0) = 0, which is injective.
Disproof: The same f and g have the property that g is not surjective but fg is.

3. A big product

Just as

$\sum_{k=a}^{b} f(k)$

represents the sum f(a)+f(a+1)+...+f(b), the notation

$\prod_{k=a}^{b} f(k)$

represents the product f(a)*f(a+1)*...*f(b).¹

Give a simple formula for the value of

$\prod_{k=1}^{n} \left(1-\frac{1}{k+1}\right)$

as a function of n, and prove that it works for all integers n >= 1.

3.1. Solution

The formula is

$\prod_{k=1}^{n} \left(1-\frac{1}{k+1}\right) = \frac{1}{n+1}$

Proof is by induction on n. The base case is n = 0, where the LHS and RHS are both 1. For the induction step, observe that

$\begin{eqnarray*} \prod_{k=1}^{n} \left(1-\frac{1}{k+1}\right) &=& \left(1-\frac{1}{n+1}\right) \prod_{k=1}^{n-1} \left(1-\frac{1}{k+1}\right) \\ &=& \frac{n}{n+1} \cdot \frac{1}{n} \\ &=& \frac{1}{n+1}. \end{eqnarray*}$

4. A big sum

Give a simple formula for the value of

$\sum_{k=1}^{n} \frac{1}{k(k+1)}$

as a function of n, and prove that it works for all integers n >= 1.

4.1. Solution

Here the tricky part is to observe that 1/(k(k+1)) = 1/k - 1/(k+1). If we sum up many of these pairs of terms, all of them except the 1/1 at the start and the -1/(n+1) at the end cancel out, giving the formula

$\sum_{k=1}^{n} \frac{1}{k(k+1)} = 1 - \frac{1}{n+1}.$

To prove that this does in fact work, use an induction on n. For n = 1 we have

$\sum_{k=1}^{1} \frac{1}{k(k+1)} = \frac{1}{2} = 1 - \frac{1}{1+1}.$

For larger n we have

latex error! exitcode was 1 (signal 0), transscript follows:

This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013)
entering extended mode
(./latex_b84f12e2406c9ce8c8848f70f70c7bce065bffc1_p.tex
LaTeX2e <2011/06/27>
Babel <3.9f> and hyphenation patterns for 78 languages loaded.
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls
Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo))
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu)
(/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu)))
No file latex_b84f12e2406c9ce8c8848f70f70c7bce065bffc1_p.aux.

! LaTeX Error: \begin{eqnarray*} on input line 7 ended by \end{document}.

See the LaTeX manual or LaTeX Companion for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.13 \end{document}
                   
! Missing $ inserted.
<inserted text> 
                $
l.13 \end{document}
                   
! Missing } inserted.
<inserted text> 
                }
l.13 \end{document}
                   
! Missing } inserted.
<inserted text> 
                }
l.13 \end{document}
                   
! Missing \cr inserted.
<inserted text> 
                \cr 
l.13 \end{document}
                   
! Missing { inserted.
<inserted text> 
                {
l.13 \end{document}
                   
! Missing $ inserted.
<inserted text> 
                $
l.13 \end{document}
                   
! Missing $$ inserted.
<to be read again> 
                   \par 
l.13 \end{document}
                   
[1] (./latex_b84f12e2406c9ce8c8848f70f70c7bce065bffc1_p.aux) )
(\end occurred inside a group at level 1)

### semi simple group (level 1) entered at line 7 (\begingroup)
### bottom level
(see the transcript file for additional information)
Output written on latex_b84f12e2406c9ce8c8848f70f70c7bce065bffc1_p.dvi (1 page,
 1120 bytes).
Transcript written on latex_b84f12e2406c9ce8c8848f70f70c7bce065bffc1_p.log.

5. A recurrence

Let T(n) = T(n/3) + n and let T(1) = 1. Give a simple formula for T(3^k) as a function of k, and prove that it works for all integers k >= 0.

5.1. Solution

Start by looking at the first few values of T(3^k). We have T(3⁰) = T(1) = 1, T(3¹) = 1 + 3, T(3²) = 1 + 3 + 9, etc. The pattern here seems to be that

$T(3^k) = \sum_{i=0}^{k} 3^i = \frac{3^{k+1} - 1}{2}.$

To verify this pattern, observe that it works for k = 0, since (3⁰⁺¹-1)/2 = (3-1)/2 = 1; and for larger k, we have T(3^k) = T(3^k/3) + 3^k = T(3^k-1) + 3^k = (3^k-1)/2 + 3^k = (3^k-1 + 2*3^k) / 2 = (3*3^k-1) / 2 = (3^k+1-1)/2 and the induction goes through.

Or 1 if b < a; see SummationNotation. (1)