Problems

Show that

$\begin{displaymath}0^2 + 1^2 + 2^2 + \cdots + n^2 = {n(n+1)(2n+1)\over 6}. \end{displaymath}$
Let be the Fibonacci numbers defined by: , , and if , $F_k = F_{k-1}+F_{k-2}$ . Show that:

$\begin{displaymath}F_{n-1}F_{n+1} = F_n^2 + (-1)^n \end{displaymath}$

and that

$\begin{displaymath}\sum_{i=0}^{n}F_i^2 = F_nF_{n+1}. \end{displaymath}$
Show that:

$\begin{displaymath}1 + {1\over \sqrt 2} + {1\over \sqrt 3} + \cdots + {1\over\sqrt n} \le 2\sqrt n. \end{displaymath}$
Show that:

$\begin{displaymath}2!\cdot4!\cdot6!\cdots(2n)! \ge ((n+1)!)^n. \end{displaymath}$
Show that:

$\begin{displaymath}\sqrt{2+\sqrt{2 + \sqrt{2+\cdots +\sqrt{2}}}} = 2\cos{\pi\over 2^{n+1}},\end{displaymath}$

where there are 2s in the expression on the left.
(Chebyshev Polynomials) Define as follows:

$\begin{eqnarray*} P_0(x) &=& 1 \\ P_1(x) &=& x \\ P_{n+1}(x) &=& xP_n(x)-P_{n-1}(x), {\rm for\ } n > 0. \end{eqnarray*}$

Show that

$\begin{displaymath}P_n(2\cos\theta) = {\sin (n+1)\theta \over \sin\theta}. \end{displaymath}$
Show that:

$\begin{displaymath}\sin\theta + \sin 2\theta + \sin 3\theta + \cdots + \sin n\th... ...Big({n\theta\over 2} \Big)\over \sin\Big({\theta\over 2}\Big)} \end{displaymath}$
(Quicksort) Prove the correctness of the following computer algorithm to sort a list of numbers into ascending order. Assume that the original list is

$\begin{displaymath}\{x_0, x_1, \ldots, x_{n-1} \}. \end{displaymath}$

Sort(,) where $j\le k$ sorts the elements from to $x_{k-1}$ . In other words, to sort the entire list of elements, call Sort(, ). (Note that Sort(, ) sorts an empty list.)
Here is the algorithm:
- (Case 1) If $k-j\le 1$ , do nothing.
- (Case 2) If , rearrange the elements from $x_{j+1}$ through $x_{k-1}$ so that the first slots in the list are filled with numbers smaller than , then put in , and then all the numbers larger than . (This can be done by running a pointer from the $(k-1)^{\mathrm th}$ slot down and from the $(j+1)^{\mathrm th}$ slot up, swapping elements that are out of order. Then put into the slot between the two lists.)
  After this rearrangement, suppose that winds up in slot , where $j\le m < k$ . Now apply Sort(,) and Sort(, ).
(Towers of Hanoi) Suppose you have three posts and a stack of disks, initially placed on one post with the largest disk on the bottom and each disk above it is smaller than the disk below. A legal move involves taking the top disk from one post and moving it so that it becomes the top disk on another post, but every move must place a disk either on an empty post, or on top of a disk larger than itself. Show that for every there is a sequence of moves that will terminate with all the disks on a post different from the original one. How many moves are required for an initial stack of disks?
(Pick's Theorem) Given a simple polygon in the plane whose vertices lie on lattice points, show that the area of the polygon is given by , where is the number of lattice points entirely within the polygon and is the number of lattice points that lie on the boundary of the polygon.
A simple polygon is a closed loop of line segments whose only points in common are the endpoints of adjacent pairs of segments. In other words, the edges of the polygon do not touch each other, except at the vertices, where exactly two edges meet. Note that a simple polygon need not be convex.

$\begin{picture}(4, 1.3)(-2,-.1) \multiput(0,0)(.2,0){9}{\circle*{.04}} \multiput... ...ne(2,1){1.6}} \put(0,.2){\line(5,-1){1}} \put(1,0){\line(3,5){.6}} \end{picture}$

In the example above, the triangle includes 6 boundary points and 12 interior points, so its area should be (according to Pick's Theorem) . You can check that this is right by noticing that its area is the area of the surrounding rectange ( $5\cdot 8 = 40$ ) less the areas of the three surrounding triangles: (5/2, 15/2, and 32/2). When we check, we get: .
(Arithmetic, Geometric, and Harmonic means) Let $A = \{a_1, a_2, \ldots, a_n \}$ be a set of positive numbers. We define the arithmetic, geometric, and harmonic means ( $\mathcal{A}(A)$ , $\mathcal{G}(A)$ , and $\mathcal{H}(A)$ , respectively) as follows:

$\begin{eqnarray*} \mathcal{A}(A) &=& {a_1 + a_2 + \cdots + a_n \over n} \\ \mat... ...playstyle a_2}+\cdots +{\displaystyle 1\over \displaystyle a_n}} \end{eqnarray*}$

Show that

$\begin{displaymath}\mathcal{H}(A) \le \mathcal{G}(A) \le \mathcal{A}(A). \end{displaymath}$

In the solution section, the actual solution is preceeded by a couple of hints.
(Catalan numbers) Given pairs of parentheses, Let be the number of ways they can be arranged in a valid mathematical expression. For example, if , there are 5 ways to rearrange the parentheses:

$\begin{displaymath}((())), (())(), ()(()), (()()), ()()(), \end{displaymath}$

so . Let . Show that:

$\begin{displaymath}T_n = {1\over n+1}{2n \choose n}. \end{displaymath}$

Hint: Show that:

$\begin{displaymath}T_{i+1} = T_iT_0 + T_{i-1}T_1 + \cdots + T_0T_i. \end{displaymath}$