BERKELEY MATH CIRCLE 2000-2001

Graph Theory, Oct. 8, 2000

PAUL ZEITZ
UNIVERSITY OF SAN FRANCISCO

1. Why is the product of three consecutive integers always divisible by 6?
2. Why is ${1^3+2^3+3^3 +\cdots + n^3= \frac{n^2(n+1)^2}{4}}$?
3. Why is the $n$th Fibonacci number equal to
   $$\frac{1}{ \sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right)^n -\left(\frac {1-\sqrt{5}}{2} \right)^n \right\}?$$

4. Fermat's Little Theorem states that if $p$ is a prime, then $\mod{a^p}{a}{p}$; in other words, $a^p-a$ is divisible by $p$. Why is Fermat's Little Theorem true?
5. De Moivre's Theorem states that
   $$(\cos \theta + i\sin\theta)^n =\cos n\theta + i\sin n\theta.$$
   Why is De Moivre's Theorem true?
6. Euler's formula states that
   $$e^{i\theta} = \cos \theta + i\sin \theta.$$
   Why is it true?
7. Why is the Fundamental Theorem of Calculus true?
8. A Problem from BAMM 2000. Consider the following experiment:
   1. First a random number $p$ between 0 and 1 is chosen by spinning an arrow around a dial which is marked from 0 to 1. (This way, the random number is ``uniformly distributed"--the chance that $p$ lies in the interval, say, from $0.45$ to $0.46$ is exactly $1/100$; and the chance that $p$ lies in the interval from $0.324$ to $0.335$ is exactly $11/1000$, etc.)

   2. Then an unfair coin is built so that it lands ``heads up" with probability $p$.
   3. This coin is then flipped 2000 times, and the number of heads seen is recorded.
   What is the probability that exactly 1000 heads were recorded?