# 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

^{0}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

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

represents the product f(a)*f(a+1)*...*f(b).^{1}

Give a simple formula for the value of

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

## 3.1. Solution

The formula is

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

# 4. A big sum

Give a simple formula for the value of

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

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

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^{0}) = T(1) = 1, T(3^{1}) = 1 + 3, T(3^{2}) = 1 + 3 + 9, etc. The pattern here seems to be that

To verify this pattern, observe that it works for k = 0, since (3^{0+1}-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)