Math 100: Problem Solving

Homework 1

Topics: Induction. Generalized induction. The pigeonhole principle.

Quiz 1 is based on one of these problems.

1. 1. Use induction to prove that \[ 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}}<2\sqrt{n}. \]

   2. Use induction to prove that $2!4!\dots(2n)!\geq((n+1)!)^n$.

2. A group of $n$ people play a round-robin tournament. Each game ends in either a win or a loss. Show that it is possible to label the players $P_1,P_2,\dots,P_n$ in such a way that $P_1$ defeated $P_2$, $P_2$ defeated $P_3$,…,$P_{n-1}$ defeated $P_n$.

3. Show that if a round-robin tournament has an odd number of teams, it is possible for every team to win exactly half its games. (Hint: Assuming the result for $2n-1$ teams, show how the same thing could happen when $2$ teams are added.)

4. For all $0\leq x\leq \pi$ and all non-negative integers $n$, prove that \[ |\sin nx|\leq n\sin x. \]

5. Show that every positive integer can be written as a sum of distinct Fibonacci numbers.

6. Let $A$ be any set of $20$ distinct integers chosen from the arithmetic progression $1,4,7,\dots,100$. Prove that there must be two distinct integers in $A$ whose sum is $104$.

7. 1. Let $S$ be a square region (in the plane) of side length $2$ inches. Show that among any nine points in $S$, there are three which are the vertices of a triangle of area $\leq\frac{1}{2}$ square inch.

   2. Nineteen darts are thrown onto a dartboard which has the shape of a regular hexagon with side length one foot. Show that two darts are within $\frac{\sqrt{3}}{3}$ feet of one another.

8. Fifteen chairs are evenly placed around a circular table on which are name cards for fifteen guests. The guests fail to notice these cards until after they have sat down, and it turns out that no one is sitting in front of their own card. Prove that the table can be rotated so that at least two of the guests are simultaneously correctly seated.

9. Let $X$ be any real number. Prove that among the numbers \[ X,2X,\dots,(n-1)X \] there is at least one that differs from an integer by at most $\frac{1}{n}$.

10. Prove that in a group of six people there are either three mutual friends or three mutual strangers. (Hint: Represent the people by the vertices of a regular hexagon. Connect vertices by a red line segment if the couple represented by these vertices are friends; otherwise, connect them with a blue line segment. Consider one of the vertices, say $A$. At least three line segments emanating from $A$ have the same color. There are two cases to consider.)

Back to contents

Homework 2

Topics: Inequalities (AM-GM, weighted AM-GM, Cauchy-Schwarz, Jensen, Hölder, Minkowski).

Quiz 2 is based on one of these problems.

1. Suppose that $a,b,c$ are positive numbers. Prove that:

   • $(a+b)(b+c)(c+a)\geq 8abc$.

   • $a^2b^2+b^2c^2+c^2a^2\geq abc(a+b+c)$.

   • If $a+b+c=1$, then $ab+bc+ca\leq\frac{1}{3}$.

2. For $0<a<b$, show that \[ (n+1)(b-a)a^n<b^{n+1}-a^{n+1}<(n+1)(b-a)b^n. \]

3. If $a,b,c$ are positive numbers, prove that \[ (a^2b+b^2c+c^2a)(a^2c+b^2a+c^2b)\geq 9a^2b^2c^2. \]

4. Suppose $a_1,\dots,a_n$ are positive numbers and $b_1,\dots,b_n$ is a rearrangement of $a_1,\dots,a_n$. Show that \[ \frac{a_1}{b_1}+\frac{a_2}{b_2}+\dots+\frac{a_n}{b_n}\geq n. \]

5. For each integer $n>2$, prove that

   • $n!<(\frac{n+1}{2})^n$,

   • $1\times 3\times 5\times\dots\times(2n-1)<n^n$.

6. • Let $x_i>0$ for $i=1,2,\dots,n$, and let $p_1,p_2,\dots,p_n$ be positive integers. Prove that \[ (x_1^{p_1}x_2^{p_2}\cdots x_n^{p_n})^{1/(p_1+\dots+p_n)}\leq \frac{p_1x_1+\dots p_nx_n}{p_1+\dots+p_n}. \]

   • Prove the same result as in the previous part holds even when the $p_i$'s are positive rational numbers.

7. Use Cauchy-Schwarz inequality to prove the following:

   • If $p_1,\dots,p_n,x_1,\dots,x_n$ are $2n$ positive numbers, \[ (p_1x_1+\dots+p_nx_n)^2\leq(p_1+\dots+p_n)(p_1x_1^2+\dots+p_nx_n^2). \]

   • If $a,b,c$ are positive numbers, \[ (a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2)\geq 9a^2b^2c^2. \]

8. Prove that for $0<a<1$, \[ (1+x)^a\leq 1+ax,\qquad x\geq-1. \] How should the inequality go when $a<0$, or when $a>1$?

9. Prove that \[ \frac{x}{1+x}<\log(1+x)<\frac{x(x+2)}{2(x+1)},\qquad x>0. \]

10. Prove that \[ \frac{\sin a}{\sin b}<\frac{a}{b}<\frac{\tan a}{\tan b},\qquad0<b<a<\frac{\pi}{2}. \]

Back to contents

Homework 3

Topics: Number theory. Modular arithmetic. The Chinese remainder theorem.

Quiz 3 is based on one of these problems.

1. 1. Prove that any two successive Fibonacci numbers $F_n$, $F_{n+1}$, $n>0$, are relatively prime.

   2. Given that $T_1=2$ and $T_{n+1}=T_n^2-T_n+1$, $n>0$, prove that $T_n$ and $T_m$ are relatively prime whenever $n\neq m$.

2. Prove $(a+b)/(c+d)$ is irreducible if $ad-bc=1$.

3. Prove that $\gcd(a_1,\dots,a_m)\gcd(b_1,\dots,b_n)=\gcd(a_1b_1,\dots,a_mb_n)$, where the parentheses on the right include all $mn$ products $a_ib_j$, $i=1,\dots,m$, $j=1,\dots,n$.

4. When Mr. Smith cashed a check for $x$ dollars and $y$ cents, he received instead $y$ dollars and $x$ cents, and found that he had two cents more than twice the proper amount. For how much was the check written?

5. Prove that any subset of $55$ numbers chosen from the set $\{1,2,\dots,100\}$ must contain numbers differing by $10$, $12$, and $13$, but need not contain a pair differing by $11$.

6. Show that $4^{3x+1}+2^{3x+1}+1$ is divisible by $7$.

7. 1. Prove that the sequence (in base-10 notation) \[ 11,111,1111,11111,\ldots \] contains no squares.

   2. Prove that the difference of the squares of any two odd numbers is divisible by $8$.

8. Prove that $(21n-3)/4$ and $(15n+2)/4$ cannot both be integers for the same positive integer $n$.

9. Complete the proof of Larson 3.2.10. (“A lattice point $(x,y)\in \mathbb{Z}^2$ is visible if $\gcd(x,y)=1$. Prove or disprove: Given a positive integer $n$, there exists a lattice point $(a,b)$ whose distance from every visible point is $\geq n$.”)

10. Prove that there does not exist an integer which is doubled when the initial digit is transferred to the end.

Back to contents

Homework 4

Topics: Fermat's little theorem, Euler's theorem. Algebra. Polynomials (factorization over different fields, Viète's relations).

Quiz 4 is based on one of these problems.

1. Let $p>5$ be a prime. Show that the number $\overbrace{11\dots11}^{p-1}$ (with $p-1$ digits of $1$) is divisible by $p$.

2. Calculate $2^{998}\pmod{121}$.

3. Let $p>5$ be a prime. Prove that $p^8\equiv1\pmod{240}$.

4. Find polynomials $F(x)$ and $G(x)$ such that \[ (x^8-1)F(x)+(x^5-1)G(x)=x-1. \]

5. Show that $x^{4a}+x^{4b+1}+x^{4c+2}+x^{4d+3}$, $a,b,c,d$ positive integers, is divisible by $x^3+x^2+x+1$. (Hint: $x^3+x^2+x+1=(x^2+1)(x+1)$.)

6. Factor $x^8+x^4+1$ into irreducibles

   1. over the rationals,

   2. over the reals,

   3. over the complex numbers.

7. Here are two results that are useful in factoring polynomials with integer coefficients into irreducibles.

   Rational-Root Theorem. If $P(x)=a_nx^n+\dots+a_0$ is a polynomial with integer coefficients, and if the rational number $r/s$ ($r$ and $s$ are relatively prime) is a root of $P(x)=0$, then $r$ divides $a_0$ and $s$ divides $a_n$.

   Gauss' Lemma Let $P(x)$ be a polynomial with integer coefficients. If $P(x)$ can be factored into a product of two polynomials with rational coefficients, then $P(x)$ can be factored into a product of two polynomials with integer coefficients

   1. Let $f(x)=a_nx^n+\dots+a_0$ be a polynomial of degree $n$ with integral coefficients. If $a_0,a_n$ and $f(1)$ are odd, prove that $f(x)=0$ has no rational roots.

   2. For what integer $a$ does $x^2-x+a$ divide $x^{13}+x+90$?

8. 1. Let $F(x)$ be a polynomial over the real numbers. Prove that $a$ is a zero of multiplicity $m+1$ if and only if $F(a)=F'(a)=\dots=F^{(m)}(a)=0$ and $F^{(m+1)}(a)\neq 0$.

   2. The equation $f(x)=x^n-nx+n-1=0$, $n>1$, is satisfied by $x=1$. What is the multiplicity of this root?

9. Given $r,s,t$ are the roots of $x^3+ax^2+bx+c=0$,

   1. Evaluate $1/r^2+1/s^2+1/t^2$, provided $c\neq 0$.

   2. Find a polynomial equation whose roots are $r^2,s^2,t^2$.

10. Prove that if $p$ is a prime, then $ab^p-ba^p$ is divisible by $p$.

Back to contents

Homework 5

Topics: Some abstract algebra (groups, rings). Summation of series. Geometric progressions. Telescoping series and products. Taylor series.

Quiz 5 is based on one of these problems.

1. If $a^{-1}ba=b^{-1}$ and $b^{-1}ab=a^{-1}$ for elements $a,b$ of a group, prove that $a^4=b^4=1$.

2. Let $R$ be a ring with identity, and let $a\in R$. Suppose there is a unique element $a'$ such that $aa'=1$. Prove that $a'a=1$.

3. Let $p$ be a prime number, and let $\ZZ_p=\{0,1,2,\dots,p-1\}$. $\ZZ_p$ is a field under the operations of addition and multiplication modulo $p$.

   1. Show that $0,1,\dots,p-1$ are the zeros of $x^p-x$ (considered as a polynomial over $\ZZ_p$). Conclude that $x^p-x=x(x-1)(x-2)\dots(x-(p-1))\pmod{p}$.

   2. Wilson's theorem. From part (a), show that \[ (p-1)!=-1\pmod{p}. \]

4. Let $n=2^{p-1}(2^p-1)$, and suppose that $2^p-1$ is a prime number. Show that the sum of all (positive) divisors of $n$, not including $n$ itself, is exactly $n$. (A number having this property is called a perfect number.)

5. Sum the series $1+22+333+\dots+n(\overbrace{11\dots1}^n)$.

6. A sequence is defined by $a_1=2$ and $a_n=3a_{n-1}+1$. Find the sum $a_1+a_2+\dots+a_n$.

7. Verify the following formula: \[ \sum_{k=1}^n\sin((2k-1)\theta)=\frac{\sin^2(n\theta)}{\sin\theta}. \]

8. Sum the following:

   1. $\displaystyle \frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\dots+\frac{n-1}{n!}$.

   2. $\displaystyle 1\times 1!+2\times 2!+3\times 3!+\dots+n\times n!$.

   3. $\displaystyle \frac{2}{1\times 2\times 3}+\frac{4}{2\times 3\times 4}+\frac{6}{3\times 4\times 5}+\dots+\frac{2n}{n(n+1)(n+2)}$.

9. Evaluate $\prod_{n=2}^\infty(1-1/n^2)$.

10. Let $F_1,F_2,\dots$ be the Fibonacci sequence. Use the telescoping property to prove \[ F_1+F_3+\dots+F_{2n-1}=F_{2n}. \]

Back to contents

Homework 6

Topics: Combinatorics. Binomial coefficients and combinatorial identities.

Quiz 6 is based on one of these problems.

1. The number 3 can be expressed as a sum of one or more positive integers, taking order into account, in four ways, namely, $3$, $1+2$, $2+1$, and $1+1+1$. Show that any positive integer $n$ can be so expressed in $2^{n-1}$ ways.

2. In how many ways can 10 be expressed as a sum of 5 nonnegative integers, when order is taken into account? (Hint: Find an equivalent problem in which the phrase “5 nonnegative integers” is replaced by “5 positive integers”.)

3. Given $n$ objects arranged in a row. A subset of these objects is called unfriendly if no two of its elements are consecutive. Show that the number of unfriendly subsets with $k$ elements is $n-k+1\choose k$. (Hint: Adopt an idea similar to that used in Larson 1.3.6.)

4. Let $a_1,a_2,\dots,a_n$ be a permutation of the set $S_n=\{1,2,\dots,n\}$. An element $i$ of $S_n$ is called a fixed point of this permutation if $a_i=i$. A derangement of $S_n$ is a permutation of $S_n$ having no fixed points. Let $g_n$ be the number of derangements of $S_n$. Show that \[ g_1=0,\qquad g_2=1, \] and \[ g_n=(n-1)(g_{n-1}+g_{n-2}),\qquad\text{for $n>2$.} \] (Hint: a derangement either interchanges the first element with another element, or it doesn't.)

5. Sum: \(\displaystyle 1-{n\choose 1}+{n\choose 2}-{n\choose 3}+\dots+(-1)^n{n\choose n}. \)

6. Sum: \(\displaystyle 1\times 2{n\choose 2}+2\times 3{n\choose 3}+\dots+(n-1)n{n\choose n}. \)

7. Sum: \(\displaystyle {n\choose 1}+2^2{n\choose 2}+3^2{n\choose 3}+\dots+n^2{n\choose n}. \)

8. Sum: \(\displaystyle {n\choose 1}-2^2{n\choose 2}+3^2{n\choose 3}-\dots+(-1)^{n+1}n^2{n\choose n}. \)

9. Prove \(\displaystyle {r\choose 0}{s\choose n}+{r\choose 1}{s\choose n+1}+{r\choose 2}{s\choose n+2}+\dots+{r\choose r}{s\choose n+r}={r+s\choose s-n}. \)

10. Prove \(\displaystyle {n\choose 0}^2+{n\choose 1}^2+{n\choose 2}^2+\dots+{n\choose n}^2={2n\choose n}. \)

Back to contents

Homework 7

Topics: Recurrent sequences (linear recurrences, generating functions). Discrete and continuous probability.

Quiz 7 is based on one of these problems.

1. Find the power series expansion for $1/(x^2+5x+6)$.

2. Solve the recurrence relation $a_0=1,a_1=0,a_2=-5$, and for $n\geq 3$ \[ a_n=4a_{n-1}-5a_{n-2}+2a_{n-3}. \]

3. Sum the finite series $a_0+a_1+\dots+a_n$, where $a_0=2,a_1=17$, and for $i>1$, $a_i=7a_{i-1}-12a_{i-2}$.

4. Solve the recurrence relation: \[ a_n=(\sqrt{a_{n-1}}+2\sqrt{a_{n-2}})^2 \] with initial condition $a_0=a_1=1$.

5. Solve the recurrence relation: \[ a_n=\sqrt{\frac{a_{n-2}}{a_{n-1}}} \] with initial condition $a_0=8,a_1=1/(2\sqrt{2})$. (Hint: Let $b_n=\ln a_n$.)

6. Find the general term formula for the sequence $(y_n)_{n\geq 0}$ with $y_0=1$ and $y_n=ay_{n-1}+b^n$ for $n\geq 1$, where $a$ and $b$ are two fixed distinct real numbers.

7. Prove the inclusion-exclusion principle: \[ |A_1\cup\dots\cup A_n|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\dots+(-1)^{n-1}|A_1\cap\dots\cap A_n| \] by induction on $n$.

8. How many positive integers less than $1000$ are not divisible by $2$, $3$, or $7$?

9. What is the probability that the sum of two (uniform) randomly chosen numbers in the interval $[0,1]$ does not exceed $1$ and their product does not exceed $\frac{2}{9}$?

10. Let $\alpha\in(0,1)$. If two points are selected (uniformly) at random from a straight line segment of length $1$, what is the probability that the distance between them is at least $\alpha$?

Back to contents

Homework 8

Topics: Geometry problems. Elementary methods. Analytic geometry, conics. Vectors and complex numbers.

Quiz 8 is based on one of these problems.

1. Let the triangle $ABC$ be inscribed in a circle, let $P$ denote the centroid of the triangle, and let $O$ denote the circumcenter. Suppose that $A,B,C$ have coordinates $(0,0)$, $(a,0)$, and $(b,c)$ respectively.

   1. Express the coordinates of $P$ and $O$ in terms of $a,b,c$.

   2. Extend the line segments $AP$, $BP$, and $CP$ to the circle in points $D$, $E$, and $F$, respectively. Show that \[ \frac{AP}{PD}+\frac{BP}{PE}+\frac{CP}{PF}=3. \] (Hint: One way to proceed is the following. Let $x$ denote $OP$, and let $R$ be the radius of the circumcircle. Then first show that \[ \frac{AP}{PD}+\frac{BP}{PE}+\frac{CP}{PF}=\frac{AP^2+BP^2+CP^2}{R^2-x^2}. \] Then express each of the terms on the right hand side in terms of $a,b,c$ (using results from the previous part).)

2. Find the relation that must hold between the parameters $a,b,c$ so that the line $x/a+y/b=1$ will be tangent to the circle $x^2+y^2=c^2$.

3. A parabola with equation $y^2=ax$ is cut in four points by the circle $(x-h)^2+(y-k)^2=r^2$. Determine the product of the distances of the four points of intersection from the axis of the parabola.

4. The sides $AD,AB,CB,CD$ of the quadrilateral $ABCD$ are divided by points $E,F,G,H$ so that $AE:ED=AF:FB=CG:GB=CH:HD$. Prove that $EFGH$ is a parallelogram.

5. On the sides of an arbitrary parallelogram, squares are constructed lying exterior to it. Prove that their centers $M_1,M_2,M_3,M_4$ are themselves vertices of a square.

6. On the sides of an arbitrary quadrilateral $ABCD$, equilateral triangles $ABM_1$, $BCM_2$, $CDM_3$, $DAM_4$ are constructed so that the first and third are exterior on the quadrilateral, while the second and fourth are on the same side of $BC$ and $DA$ as the quadrilateral itself. Prove that the quadrilateral $M_1M_2M_3M_4$ is a parallelogram.

7. In a tetrahedron, two pairs of opposite edges are orthogonal. Prove that the third pair of opposite edges must also be orthogonal.

8. Given a point $P$ on the circumference of a unit circle and the vertices $A_1,A_2,\dots,A_n$ of a regular polygon of $n$ sides inscribed in the unit circle, prove that $PA_1^4+PA_2^4+\dots+PA_n^4$ is constant (i.e., independent of the position of $P$ on the circumference).

9. Let $G$ be the centroid of a triangle $ABC$. Prove that \[ 3(GA^2+GB^2+GC^2)=AB^2+BC^2+CA^2. \]

10. Let $ABCDEF$ be a hexagon in a circle of radius $r$. Show that if $AB=CD=EF=r$, then the midpoints of $BC$, $DE$, and $FA$ are the vertices of an equilateral triangle.

Back to contents

Homework 9

Topics: Differential calculus. The extreme value theorem and the mean value theorem. Functional equations. Integral calculus. Approximating integrals by Riemann sums. Integral functional equations.

Quiz 9 is based on one of these problems.

1. A real valued continuous function satisfies for all real $x$ and $y$ the functional equation \[ f(\sqrt{x^2+y^2})=f(x)f(y). \] Prove that $f(x)=[f(1)]^{x^2}$. [Hint: First prove the theorem for all numbers of the form $2^{n/2}$ where $n$ is an integer. Then prove the theorem for all numbers of the form $\sqrt{m/2^n}$, $m$ an integer, $n$ a non-negative integer.]

2. Let $f$ be defined in the interval $[0,1]$ by \[ f(x)=\begin{cases} 0&\text{if $x$ is irrational,}\\ 1/q&\text{if $x=p/q$ (in lowest terms).} \end{cases} \]

   1. Prove that $f$ is discontinuous on each rational number in $[0,1]$.

   2. Prove that $f$ is continuous on each irrational number in $[0,1]$.

3. Suppose $f\from [0,1]\to[0,1]$ is continuous. Prove that there exists a number $c$ in $[0,1]$ such that $f(c)=c$.

4. A rock climber starts to climb a mountain at 7am on Saturday and gets to the top at 5pm. He camps on top and climbs back down on Sunday, starting at 7am and getting back to his original starting point at 5pm. Show that at some time of day on Sunday he was at the same elevation as he was at that time on Saturday.

5. Define $f$ by \[ f(x)=\begin{cases} x^2\sin(1/x)&\text{if $x\neq 0$,}\\ 0&\text{if $x=0$.} \end{cases} \] Let $g(x)=x+2f(x)$. Show that $g'(0)>0$ but that $g$ is not monotonic in any open interval about $0$.

6. 1. Show that $5x^4-4x+1$ has a root between $0$ and $1$.

   2. If $a_0,a_1,\dots,a_n$ are real numbers satisfying \[ \frac{a_0}{1}+\frac{a_1}{2}+\dots+\frac{a_n}{n+1}=0, \] show that the equation $a_0+a_1x+\dots+a_nx^n=0$ has at least one real root.

7. Evaluate $\lim_{n\to\infty}4^n(1-\cos({\theta}/{2^n}))$.

8. Calculate \[ \lim_{x\to\infty}x\int_0^xe^{t^2-x^2}\,dt. \]

9. Evaluate each of the following:

   1. $\displaystyle{\lim_{n\to\infty}\big(\frac{n}{1^2+n^2}+\frac{n}{2^2+n^2}+\dots+\frac{n}{n^2+n^2}\big).}$

   2. $\displaystyle{\lim_{n\to\infty}\Big(\big(1+\frac{1}{n}\big)\big(1+\frac{2}{n}\big)\dots\big(1+\frac{n}{n}\big)\Big)^{1/n}.}$

10. Let $f\from[0,1]\to(0,1)$ be continuous. Show that the equation \[ 2x-\int_0^xf(t)\,dt=1 \] has one and only one solution in the interval $[0,1]$.

Back to contents

Induction

1. \( \frac{1}{n+1}+\dots+\frac{1}{2n}=1-\frac{1}{2}+\frac{1}{3}-\dots+\frac{1}{2n-1}-\frac{1}{2n}. \)

2. $2^n\geq n^2\qquad\forall n\geq 4$.

3. Complement of $n$ lines in $\RR^2$ can be checkerboard colored.

4. Assume Bertrand Postulate, there is a prime $p$ between $x$ and $2x$ for all integers $x$. Prove that every natural number can be written as a sum of distinct primes or $1$.

5. Fibonacci sequence $F_1=F_2=1$, $F_{n+1}=F_n+F_{n-1}$. Show $F_{2n+1}=F_{n+1}^2+F_n^2$.

6. Every triangle can be cut into $n\geq 6$ triangles similar to it.

7. $V-E+F=2$ for connected planar graphs.

Back to contents

Pigeonhole Principle

1. 5 points chosen in a triangle of side length 2; some two are within distance 1.

2. 50 distinct positive integers chosen less than 99. Some two add up to 99.

3. $n$ people are at a party. Show some two know the same number of people.

4. Each point in the plane is colored red-blue. Some two points at distance 1 have same color. Also works with 3 colors.

5. 5 points are chosen from a 2D lattice $\Lambda$. The midpoint of some two is also on $\Lambda$.

6. $\{x\}\in[0,1)$ is the fractional part. For irrational $\alpha$, $\{n\alpha\}$ is dense in $[0,1]$.

Back to contents

Inequalities

1. AM-GM, proof by induction.

2. Weighted AM-GM.

3. Generalization. If $f$ continuous with $f(\frac{x_1+x_2}{2})\geq \frac{f(x_1)+f(x_2)}{2}$, then $f(\frac{\sum p_ix_i}{\sum p_i})\geq \frac{\sum p_if(x_i)}{\sum p_i}$.

4. These sort of functions are called concave. Appear from $C^2$ functions with $f''\leq 0$. Jensen's inequality. Proof uses mean value theorem. \[ (f(x_2)-f(\frac{x_1+x_2}{2}))-(f(\frac{x_1+x_2}{2})-f(x_1))=\frac{x_1-x_2}{2}(f'(y_2)-f'(y_1))=\frac{x_1-x_2}{2}(y_2-y_1)f''(z)\leq 0. \]

5. Apply to $f(x)=\ln x$ to get AM-GM by applying $\exp$ to both sides.

6. Basic inequality, if $f$ is $C^1$ and $f'\geq 0$, then $f$ is increasing.

7. Prove $2\sin x+\tan x\geq 3x$ for $0\leq x< \pi/2$.

8. Taylor expansion. $(1+x)^p\leq 1+px$ if $x> -1,0<p<1$.

9. Maximize area $ab$ for fencing in the shape of a rectangle divided into two parts by a vertical segment, with total fence length $3a+2b=1000$.

10. Generalizations of AM-GM. $\big(\frac{\sum p_ix_i^k}{\sum p_i}\big)^{1/k}$ is increasing in $k$. Mention special cases $k=0,\pm 1,2,\pm\infty$ (GM, AM, HM, QM, max, min).

11. For $a,b,c>0$, \[ \frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}\geq\frac{3}{2}. \]

12. Cauchy-Schwarz inequality. Difference is a sum of squares $\sum_{i<j}(a_ib_j-a_jb_i)^2$. Equality if proportional.

13. Geometric interpretation. $|\vec{a}\cdot\vec{b}|=|\vec{a}||\vec{b}|\cos\theta$.

14. Cauchy-Schwarz is equivalent to weighted AM-QM.

15. Triangle inequality. For $a,b,c$ sides of a triangle, show $(a+b-c)(b+c-a)(c+a-b)\leq abc$. Useful substitution $x=b+c-a$, etc.

16. Sides of a triangle. Show $2(a^2+b^2+c^2)\leq (a+b+c)^2$.

17. Hölder inequality (generalization of Cauchy-Schwarz). For $1/p+1/q=1$, \[ \sum |a_ib_i|\leq (\sum_i|a_i|^p)^{1/p}(\sum_i|b_i|^q)^{1/q} \]

18. Minkowski inequality (generalization of triangle inequality). For $p\geq 1$, \[ (\sum |a_i+b_i|^p)^{1/p}\leq (\sum |a_i|^p)^{1/p}+(\sum |b_i|^p)^{1/p}. \]

Back to contents

Number theory

1. Euclidean algorithm for $\gcd$. Unique decomposition $a=qb+r$ (Euclidean domain). Corollary: $\{sa+tb\mid s,t\in\ZZ\}=\ZZ\langle\gcd(a,b)\rangle$. Do for $a=90,b=65$.

2. Find all solutions of $ax+by=c$ ($x=x_0+bt/d,y=y_0-at/d$). Do $18x+32y=6$.

3. Prove $\frac{21n+4}{14n+3}$ is irreducible.

4. Prove $\sqrt{3}$ irrational. Do $\sqrt{2}+\sqrt{3}$.

5. Unique factorization into primes. Need $p\mid ab\implies p\mid a\text{ or }p\mid b$.

6. Prove $\gcd(a,b)\mathrm{lcm}(a,b)=ab$.

7. Modular arithmetic, residue classes $\pmod n$, $\ZZ/n$. Notation, $x\equiv y\pmod n$. Calculate $142+(15\cdot 72)\pmod 7$.

8. Every odd square is $1\pmod 8$.

9. Infinitely many primes. Euclid $p_1\cdots p_k+1$. Infinitely many primes $3\pmod 4$. $4p_1\cdots p_k-1$.

10. Last digit of $7^{\text{current year }20xx}$.

11. Divisibility rule of $9$ and $11$. Calculate $1745002145$ modulo $9$ and $11$.

12. Fermat's little theorem. $a^p\equiv a\pmod p$, better version: $a^{p-1}\equiv 1\pmod p$ for $\gcd(a,p)=1$. Calculate $2^{233}\pmod {47}$.

13. Generalization $a^{\varphi(n)}\equiv 1\pmod n$, $\varphi$ is Euler's totient function. Proof: If $b_1,\dots,b_{\phi(n)}$ are coprime residue classes $\pmod n$, so are $ab_1,\dots,ab_{\phi(n)}$.

14. $n=p_1^{a_1}\cdots p_k^{a_k}$. Then $\varphi(n)=n(1-1/p_1)\cdots(1-1/p_k)$ by principle of inclusion exclusion. Calculate $17^{81}\pmod {60}$.

15. Number of divisors $\tau(n)=(1+a_1)\cdots(1+a_k)$. Find smallest integer with exactly $28$ divisors.

16. Sum of divisors $\sigma(n)=\prod_i \frac{p_i^{a_i}-1}{p_i-1}$. Do $n=1000$.

17. Highest power of $3$ dividing $100!$, $\lfloor n/p\rfloor +\lfloor n/p^2\rfloor +\cdots$.

18. For any $55$ numbers from $\{1,\dots,100\}$, some two must differ by $9$.

19. Chinese remainder theorem. $m_1,\dots,m_n$ pairwise relatively prime, and $a_i\in\ZZ$. There is some $x$ with $x\equiv a_i\pmod {m_i}$.

20. There are a million consecutive integers none of which is a prime power.

21. For $p$ prime, each prime factor of $2^p-1$ is bigger than $p$ (so infinitely many primes).

22. If $m$ odd, $m\mid 2^{(m-1)!}-1$. $\varphi(m)\mid (m-1)!$.

Back to contents

Algebra

1. Groups. Typical example symmetric group $S_n$. Also $(\RR,+),(\RR^*,\cdot)$.

2. If $(ab)^3=1$, show $(ba)^3=1$.

3. If $aba=ba^2b,a^3=1,b^3=1$, show $b=1$.

4. Ring, always with $1$. Typical example $n\times n$ matrices $M_n(\RR)$. Define center $Z(R)$.

5. Commutative ring. Typical examples $\ZZ,\ZZ/n$.

6. If $x^2-x\in Z(R)$ for all $x$, then $R$ is commutative.

7. Integral domain if no zero divisor. Typical example $\ZZ, \ZZ[\sqrt{2}],\ZZ[X]$, not $\ZZ/6$.

8. Field. Example $\QQ,\RR,\CC,\ZZ/p,\QQ[\sqrt{2}]$.

9. $D[X]$ is a domain if $D$ is.

10. Euclidean domain, $\mathbb{F}[X]$ but not $\ZZ[X]$ (division algorithm in $\ZZ[X]$ works for monic polynomials). Example: $x^5+3x^2+1=(2x^3-x+1)(x^2/2+1/4)+(5x^2/2+x/4+3/4)$.

11. Euclidean domains are unique factorization domains, as is $D[X]$ for any integral domain $D$ up to multiplication with elements in $D$ (can work in quotient field of $D$).

12. Find $\gcd(x^8-1,x^5-1)=x-1$ by Euclidean algorithm.

13. Find $P\in\QQ[X]$ with $x^2+1\mid P(x)$ and $x^3+x^2+1\mid P(x)+1$.

14. Over an integral domain, factor theorem: $P(\alpha)=0$ iff $x-\alpha\mid P(x)$.

15. Unique factorization for $\ZZ,\QQ,\RR,\CC$. Fundamental theorem of algebra for $\RR,\CC$.

16. For what $n$ is $x^{4n}-2x^{n}+1$ divisible by $x^2+1$?

17. Identity theorem. If $\mathrm{deg}\leq n$ polynomials $P,Q$ have $P(\alpha_i)=Q(\alpha_i)$, $i=0,\dots,n$, then $P=Q$.

18. Find all $P\in\RR[X]$ with $P(x^2+1)=P(x)^2+1$ and $P(0)=0$.

19. Gauss' Lemma for $\ZZ$ (a rational factorization produces an integer factorization)

20. Vi\‘ete relations, relating symmetric polynomials of roots to coefficients. Find polynomial for the squares of roots of $x^2+ax+b$.

21. $a_nx^n+\dots+a_3x^3+x^2+x+1$ does not have all real roots.

22. Wilson's theorem $(p-1)!\equiv -1\pmod p$.

Back to contents

Series

1. $a+ax+\dots+ax^n$, then as $x\to\infty$. Define partial sums.

2. $\cos\theta+\dots+\cos n\theta$.

3. Telescoping. $\sum a_n$, with $a_n=b_{n-1}-b_n$. If $b_n\to 0$, then converges.

4. $\sum \frac{1}{n(n+1)}$.

5. Prove $F_1+F_2+\dots+F_n=F_{n+2}-1$.

6. $\prod_{n=2}^\infty \frac{n^3-1}{n^3+1}$.

7. Series for $(1+x)^n$. $\sum_i {n\choose i}$, $\sum_i (-1)^i{n\choose i}$, $\sum_k {m\choose {r-k}}{n\choose k}={{m+n}\choose r}$.

8. Taylor series. Recalls (finite) Taylor's theorem. Do $e^x,\cos x,\sin x,\log(1+x),(1+x)^r$ (for arbitrary $r\neq 0$).

9. Geometric again $\sum x^n=1/(1-x)$. Do $\sum nx^{n-1}$, $\sum x^n/n$.

10. $e$ is irrational.

11. Power series $\sum_n a_n x^n$. Radius of convergence.

12. $\sum F_n/3^n$. Then write $f(x)=\sum_{n\geq 0}F_nx^n=x+x^2+2x^3+\cdots$, and by recurrence, $f(x)=\frac{x}{1-x-x^2}$.

Back to contents

Combinatorics

1. $n!$, permutation of $n$ elements, number of bijective functions $\{1,\dots,n\}\to\{1,\dots,n\}$.

2. $n^k$, $k$ ordered (not necessarily distinct) elements from $\{1,\dots,n\}$, number of functions $\{1,\dots,k\}\to\{1,\dots,n\}$. Number of 4-letter words $26^4$.

3. $n!/(n-k)!$, $k$ ordered distinct elements from $\{1,\dots,n\}$, number of injective functions $\{1,\dots,k\}\to\{1,\dots,n\}$.

4. ${n\choose k}$, $k$ unordered distinct elements from $\{1,\dots,n\}$, number of (strictly) increasing functions $\{1,\dots,k\}\to\{1,\dots,n\}$.

5. ${n+k-1}\choose k$, $k$ unordered (not necessarily distinct) elements from $\{1,\dots,n\}$, number of (not necessarily strictly) increasing functions $\{1,\dots,k\}\to\{1,\dots,n\}$, same as number of strictly increasing functions $\{1,\dots,k\}\to\{1,\dots,n+k-1\}$.

6. ${n\choose k}={n\choose n-k}$, chosen set vs its complement.

7. $k{n\choose k}=n{{n-1}\choose{k-1}}$, a set and an element in it.

8. ${n\choose k}={{n-1}\choose k}+{{n-1}\choose{k-1}}$, a fixed element is chosen or not, Pascal's triangle.

9. $\sum_k {m\choose {r-k}}{n\choose k}={{m+n}\choose r}$, choose $r$ elements from $m$ elements and $n$ elements.

10. $\sum k{n\choose k}$, differentiate $(1+x)^n$, or use $k{n\choose k}=n{{n-1}\choose {k-1}}$.

11. $\sum \frac{1}{k+1}{n\choose k}$, integrate, or use $\frac{1}{n+1}{{n+1}\choose {k+1}}=\frac{1}{k+1}{n\choose k}$.

12. ${{n+k+1}\choose k}={n\choose 0}+{{n+1}\choose 1}+\dots+{{n+k}\choose k}$. Induct on $k$. Alternatively, choose a subset $S$ of size $k$ from $\{1,\dots,n+k+1\}$, and break it up by the largest number outside of $S$.

13. Principle of inclusion exclusion.

14. Number of surjective functions $\{1,\dots,k\}\to\{1,\dots,n\}$. If $A_i$ is the set of functions that don't hit $i$, then the number is $n^k-|A_1\cup\cdots A_n|$. Use inclusion exclusion to get $\sum_i (-1)^i{n\choose i}(n-i)^k$.

Back to contents

Recurrences

1. Fibonacci sequence $f(x)=\sum F_n x^n$, $f(x)=\frac{x}{1-x-x^2}$. Break into partial fractions, $\frac{x}{1-x-x^2}=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x}$, where $\alpha,\beta$ solutions to $z^2-z-1$ (characteristic equation). Get $F_n=\frac{1}{\sqrt{5}}\big(\big(\frac{1+\sqrt{5}}{2}\big)^n-\big(\frac{1-\sqrt{5}}{2}\big)^n\big)$.

2. Number of ways of tiling $2\times n$ board with $2\times 1$ dominoes, $F_{n+1}$.

3. General linear recurrences. Distinct roots, repeated roots.

4. $a_n=4a_{n-1}-4a_{n-2}$, $a_0=a_1=1$.

5. $a_n=3a_{n-1}-4a_{n-3}$, $a_0=30,a_1=-10,a_2=20$.

6. Linear recurrence with additional term. General solution plus one particular solution. $a_n=3a_{n-1}+1$.

7. Putnam problem, $a_1=1,a_2=2,a_3=24$, $a_n=\frac{6a_{n-1}^2a_{n-3}-8a_{n-1}a_{n-2}^2}{a_{n-2}a_{n-3}}$. Show $a_n$ is an integer divisible by $n$.

8. Catalan numbers, $C_n$ is number of ways of parenthesizing $n+1$ variables with $n-1$ bracket pairs, number of binary trees with $n+1$ leaves, number of crossingless matchings on $2n$ strands, number of paths from $(0,0)$ to $(n,n)$ on or below the diagonal.

9. Recurrence $C_{n+1}=\sum_{k=0}^n C_kC_{n-k}$. So if $f(x)=\sum C_n x^n$, $1+xf(x)^2=f(x)$, $f(x)=\frac{1-\sqrt{1-4x}}{2x}$. Do expansion to get $C_n=\frac{1}{n+1}{{2n}\choose n}$.

Back to contents

Probability

1. Probability a function $\{1,2,3\}\to\{1,2,3,4,5\}$ is injective.

2. Cashier (with no money initially) is selling $2n$ $\$5$ tickets, and $n$ people bring $\$5$ notes, and $n$ people bring $\$10$ notes. Probability of success $\frac{1}{n+1}$.

3. Probability 2 people have the same birthday, more likely than not at $23$ people.

4. Real number picked from $[0,1]$, probability it is less than $1/3$? Need to assume picked uniformly.

5. Probability a point from $[0,1]^2$ is within distance $1/5$ to the middle?

6. Pick $x,y\in[0,1]$, probability $y\leq x^2$? Assume picked uniformly and independently.

7. Two people arrive (uniformly) between 4 and 5, and each waits 15min and then leaves. Probability they will meet.

8. Length one needle dropped on infinitely many horizontal lines at distance 2 apart. Probability it hits a line.

9. Cut a length $d$ bar into three pieces. Probability they form a triangle. If we picked 2 points $x,y$ (wlog $x<y$) simultaneously and cut there, each of the sidelengths $x,y-x,d-y$ has to be less than the semiperimeter $d/2$. But if first cut at one point $x$ (wlog $x>d/2$), then cut the larger piece at $\alpha x$, then each of the side lengths $\alpha x,(1-\alpha)x,d-x$ is less than $d/2$.

Back to contents

Geometry

1. Medians of a triangle intersect by Euclidean geometry.

2. Same using coordinate geometry. Take $A=(a_1,a_2)$, similarly.

3. By translation, rotation, scaling, can assume $B=(0,0),C=(1,0)$.

4. Drop perpendiculars $PA,PB,PC$ from $P=(a,b)$ to a parabola. The centroid of $\Delta ABC$ is on the axis.

5. Find the slope one tangents to the ellipse $3x^2+y^2=3$.

6. Vector addition, points between two points, $\alpha \vec{v}+(1-\alpha)\vec{w}$.

7. Medians intersect using vectors.

8. $D,E,F$ chosen on the sides of $\Delta ABC$ with $AF/AB=BD/BC=CE/CA$. Centroids of $\Delta ABC$ and $\Delta DEF$ agree.

9. $AB=AC$, $D$ midpoint of $BC$, $DE$ perpendicular to $AC$, $F$ midpoint of $DE$. Prove $AF\perp BE$.

10. Suppose altitudes $AP$ and $BQ$ of a tetrahedron $ABCD$ are coplanar. Show $AB\perp CD$.

11. $ABCD$ parallelogram, $F$ midpoint of $CD$, $AF$ intersects $BD$ in $E$. Prove $DE=DB/3$.

12. Complex conjugates, Cartesian coordinates for addition, polar coordinates for multiplication, unit circle, roots of unity.

13. Find $z_3$, given two other points $z_1,z_2$ of an equilateral triangle, $z_3=-z_1\omega-z_2\omega^2$.

14. Draw equilateral triangles $BDC,CEA,AFB$ outside a triangle $ABC$. Show centroids of the three new triangles form an equilateral triangle.

15. $P,Q,R,S$ centers of squares drawn outside a quadrilateral $ABCD$. Show $PR\perp QS$ and $|PR|=|QS|$.

16. Regular polygon $A_1A_2\cdots A_n$ of circumradius $r$, $P$ some other point on the circumcircle. Show $\sum_k |PA_k|^2=2nr^2$.

Back to contents

Analysis

1. Continuity, different definitions, $\sin\frac{1}{x}$ discontinuous.

2. Intermediate value property (IVT), extreme value property.

3. Given two polygons, there is a line that cuts both in equal areas.

4. Continuous $f$ with $f(x+y)=f(x)+f(y)$ must be $f(x)=ax$.

5. Continuous $f$ with $f(x)=f(x^2)$ must be constant.

6. A runner runs 6 miles in 30 minutes. Show he ran one mile in exactly 5 minutes.

7. Find all continuous functions $f\colon[0,\infty)\to\RR$ with $f(xy)=xf(y)+yf(x)$.

8. Example of (discontinuous) function with $f(x+y)=f(x)+f(y)$ but $f(x)\neq ax$.

9. Derivatives. $x^2\sin\frac{1}{x}$, $f'$ exists but is not continuous.

10. Rolle's theorem, mean value theorem, Taylor's theorem.

11. $f=x^3-3x+a$ cannot have more than one zero in $[-1,1]$.

12. Show $4ax^3+3bx^2+2cx-(a+b+c)$ has a root in $[0,1]$.

13. $P,Q$ points on unit circle, $R$ perpendicular from $Q$ to the tangent through $P$, maximize area of $\Delta PQR$.

14. Putnam problem, show all roots of $P(x)=1+8x+16x^2+8x^3+x^4$ are real.

15. Find number of solutions of $x^2-x\sin x-\cos x=0$.

16. Find $\int_2^4 \frac{\sqrt{\ln(9-x)}\,dx}{\sqrt{\ln(9-x)}+\sqrt{\ln(x+3)}}$.

17. L'Hospital, $f/g$, both going to zero, or both going to infinity, $\lim_{x\to 0}(\frac{1}{\sin x}-\frac{1}{x})$.

18. $\lim_{n\to\infty}(1+\frac{1}{n})^n$.

19. $\lim_{x\to 0}x^x$,

20. Fundamental theorem of calculus, $\lim_{x\to 0}\frac{1}{x}\int_0^x(1+\sin 2t)^{1/t}dt$.

21. Find all $f$ satisfying $f(x)=\int_0^x f(t)dt+1$.

22. $\int_0^x f(t)dt=\int_x^1t^2f(t)dt+x^{16}/8+x^{18}/9+C$.

23. $\lim_{n\to\infty}\big(\frac{1}{2n+1}+\dots+\frac{1}{3n}\big)$.

24. $\lim_{n\to\infty}\sum_{k=1}^n\frac{1}{\sqrt{k^2+n^2}}$.

25. $\lim_{n\to\infty} \frac{\sqrt{1}+\sqrt{2}+\dots+\sqrt{n}}{\sqrt{n^3}}$.

26. Find integral part (floor) of $S=\sum_{1}^{10^9} n^{-2/3}$.

27. $f$ differentiable, $f(0)=0$, and $f'$ strictly increasing (don't know if $f''$ exists). Show $f(x)/x$ is strictly increasing for $x>0$.

28. Find $I=\int_0^{\pi}\frac{x\sin x}{1+\cos^2 x}dx$.

29. Putnam problem, $f\colon[1,3]\to\RR$, $|f(x)|\leq 1$, $\int_1^3 f(x)dx=0$. Maximum value of $\int_1^3\frac{f(x)}{x}dx$.

Back to contents