If you find a mistake, omission, etc., please let me know by e-mail.

• Introductions, à la Pál Erdös: “What's your name and what's your problem?”
  (from our e-mail correspondence; see the list above, plus Zach on injective polynomials and me on sphere packings, and more details on some of the other favorites)
• Expectations, and organizational / administrative details
• Some initial problems to think about: three 5x5 and three 7x7 Kenken puzzles; which of 5^1/2 + 13^1/2 and 34^1/2 is larger?

September 14

• Various approaches to 5^1/2 + 13^1/2 vs. 34^1/2. How were these numbers 5, 13, 34 chosen? Generalizations and connections: factoring x²+1 or x²-1; Fibonacci numbers; the general formula for a^1/2 + b^1/2 vs. c^1/2 via the sign of D(a,b,c) := a² + b² + c² - 2 (ab + ac + bc), with unexpected extra symmetry, in turn leading us to Heron's formula for the area of a triangle of sides a^1/2, b^1/2, c^1/2 (if it exists); we know how to make D(a,b,c)=4 or -4, but can we make |D(a,b,c)| even smaller (but not zero) for some natural numbers a,b,c?
• Solving two of the Kenken puzzles
• General considerations I: The uses of problems, to proposers and solvers, ranging from external applications to the satisfaction of solving a stumper; who is playing the “game” (proposer? other solvers? audience for solution?), and how this and other aspects of the context of the problem might influence one's strategy for solving and presenting the solution

September 21

• Progress report on small nonzero |D(a,b,c)| values: D(1,1,1) = -3, not directly of much use for our purpose (since 1^1/2 + 1^1/2 vs. 1^1/2 is even less impressive than 1^1/2 + 1^1/2 vs. 2^1/2), but suggestive: using narrow triangles on a triangular grid instead of a square one, we can get bigger examples such as D(3,7,19) = -3. But can we make |D| as small as 1 or 2 (or for that matter solve D(a,b,c) = +3 ?)
• Inequalities in general; different approaches to the maximum of x-x² (a.k.a. xy if x+y=1, which reveals a symmetry between x and 1-x); when solving an inequality problem, always try to determine the equality condition.
• More on the triangle inequality: some further applications (reflection, bug on a Rubik's cube -- can we make this one trickier?), and the surprising difficulty of the Euclidean proof. Proving it algebraically, in effect via D( x₁² + y₁², x₂² + y₂², (x₁+x₂)² + (y₁+y₂)² ) = -4 (x₁y₂-x₂y₁)² [sorry, HTML doesn't handle expressions like x₁² as well as TeX...]. Along the way we find that (x₁x₂+y₁y₂)² ≤ (x₁²+y₁²) (x₂²+y₂²), which is one way to state the 2-dimensional case of the Cauchy-Schwarz inequality, whose importance and ubiquity in mathematics are hard to overstate. Equality holds if and only if x₁y₂=x₂y₁, which is to say if and only if the vectors (x₁, y₁) and (x₂, y₂) are proportional. In 3 dimensions, we find with a little more work that D( x₁² + y₁² + z₁², x₂² + y₂² + z₂², (x₁+x₂)² + (y₁+y₂)² + (z₁+z₂)² ) equals -4 times (x₁y₂-x₂y₁)² + (y₁z₂-y₂z₁)² + (z₁x₂-z₂x₁)²; so we get the triangle inequality for vectors (x₁, y₁, z₁) and (x₂, y₂, z₂), with equality if and only if one is a nonnegative multiple of the other, and also three-dimensional Cauchy-Schwarz: (x₁x₂+y₁y₂+z₁z₂)² ≤ (x₁²+y₁²+z₁²) (x₂²+y₂²+z₂²) with equality if and only if the vectors are proportional. To do it in general, either proceed in the same way, ending up with a sum of (n²-n)/2 squares [where did I get this count of (n²-n)/2?], or use the trick with the quadratic formula and the nonnegativity of |a₁v₁ + a₂v₂|² -- as we did earlier for x-x².
• Sample applications:
  • The formula for the angle between two nonzero vectors v,v' (it's the angle whose cosine is <v,v'>/|v||v'|, where <v,v'> is the “dot product” (a.k.a. “inner product”, “scalar product”) of v and v'.
  • Also, in three dimensions, the difference (x₁y₂-x₂y₁)² + (y₁z₂-y₂z₁)² + (z₁x₂-z₂x₁)²; is the squared length of the “cross product” of the two vectors.
  • Using Cauchy-Schwarz to find the distance from the origin to a line or plane, and the minimum of 1/a + 1/b + 1/c over positive numbers a, b, c subject to a + b + c = 30.
  For most of this last group of examples, you could (but don't really want to) alternatively find the minimum using standard tools of differential calculus.

October 5

• Solution by Cauchy-Schwarz of a geometric minimization problem: given a triangle, find point in the interior minimizing the sum of inverse distances to the three sides.
• Geometric solution of the problem of minimizing the sum of distances from a point to the three vertices of an acute triangle, leading to the Fermat point and some of the remarkable properties of an associated configuration of three equilateral triangles. Physical (vector field) interpretation. Students' suggested variations and generalizations (and some comments):
  • minimize a weighted sum of distances? [careful that the weights aren't too lopsided!]
  • minimize the sum of the squared distances, or of the distances' inverses? [the latter might not have a very simple solution]
  • drop the hypothesis that the triangle be acute, or that the point be inside the triangle?
  • instead of a triangle, how about four or more points? Four actually turns out to be easier! [But 5 or more is known to be intractable, though special cases can be done, e.g. a regular n-gon, or a hexagon ABCDEF whose diagonals AD,BE,CF meet at a point]
  • [while we're at it, imagine four points in space, or five in hyperspace, etc.]
• The “quadrilateral inequality” encountered during the geometrical solution suggest a segue to the important technique of induction. Base case (S_n0), inductive hypothesis (S_k), inductive step (S_k implies S_k+1). Variation: “strong induction” (equivalently: apply induction to the statement S_n: “S_k is true for each k between n₀ and n” rather than to S_n itself). Standard examples of induction problems: sums and and other recursions, once we've guessed the answer from the pattern of the first few examples (an important problem-solving technique in general, but beware of false trails such as 3²+4²=5²,   3³+4³+5³=6³,  but   3⁴+4⁴+5⁴+6⁴≠7⁴); maximal number of slices of a soap pizza produced by n straight cuts; the inductive proof of Fermat's little theorem (and another misleading pattern: 341=11*31 is the first (counter)example where 2^p-2 is a multiple of p but p is not prime).

October 15
More about induction, mostly motivated by Pascal's triangle:

• Sometimes we want to prove some S_n, but must find a more general statement T_n for which T_k implies T_k+1 (and not just S_k+1!) to make the induction work (and that's also one trick for making an induction problem harder);
• Various techniques for guessing the pattern to prove inductively, ranging from special cases to solving for the coefficients to searching for the sequence online on Google or, better yet, the OEIS = Online Encyclopedia of Integer Sequences);
• Induction and its variants as a basic structural property of the natural numbers;
• Avoiding (or more honestly, hiding) induction: having established inductively basic results such as the distributive law for arbitrarily long sums, or telescoping cancellation, use those results rather than explicitly carry out a new induction proof.

October 19

• The equivalence of “infinite descent” with induction (via “strong induction”); the grounding of both of these techniques in the “well-ordering” of the set {0,1,2,3,...} of whole numbers (totally ordered [trichotomy], and every nonempty subset has a minimum). Finite well-ordered sets determined up to isomorphism by their cardinality; infinite sets, not so, even countably infinite ones, e.g. {0,1,2,3,...,ω} and much more complicated examples (anyone for ω^ωω?).
• Proof by infinite descent that if b and c are positive integers such that |c² - bc - b²| = 1 then b and c are consecutive Fibonacci numbers. The converse was seen by induction last week. Any Fibonacci-mutant sequence with a different initial pair, e.g.\ the Lucas sequence 1, 3, 4, 7, 11, 18, ..., has the analogous property that the value of |c² - bc - b²| at consecutive pairs (b,c) is constant; this can be shown either by induction, or by writing (b,c) as a linear combination of the initial pair whose coefficients are (non-mutant) Fibonacci numbers [this too uses induction] and then doing some algebra. Does the converse hold again?
• Introduction to generatingfunctionology (yes, the single-word typesetting is a joke, but blame Wilf for it, not me), via Pascal's triangle again: (1+x)ⁿ as a generating polynomial for the nth row, proved by induction and used to re-explain the fact that the sum of all the entries in that row is 2ⁿ and to find the sum of their squares via the xⁿ coefficient of (1+x)ⁿ (1+x)ⁿ = (1+x)²ⁿ.

October 26

• Go over some of the generating-polynomial problems from last week. Is there a more intuitive explanation for the formula for the sum over j=0,1,2,...,n of Binomial(n, j)²? An unexpected solution to the King-path enumeration problem using powers of a 32x32 “transfer matrix” --- a useful technique (which was a mainstay of my Math and Chess seminar some years ago), and an example of what's called “dynamical programming”, though here needlessly complicated, being equivalent to a more familiar approach (a Pascal-like triangle with three choices at each point instead of Pascal's two) and also to a 7x7 transfer matrix that keeps track only of columns. Any of these methods will also handle the variant of counting 7-move paths to f8 or g8, though the discrepancy between the answer and the enumeration on an unbounded board still takes some other ideas to explain.
• A further matrix-power digression: a simple 2x2 matrix whose powers give Fibonacci numbers and explain (via determinants) why F_n-1F_n+1 - F_n² = (-1)ⁿ. It even works for negative n once we've figured out what F_n should be for n<0.
• Basic examples of generating functions (other than polynomials) and operations on them, including multiplication which corresponds to convolution of the coefficient sequences. [BTW this is useful even for generating polynomials, e.g. for the distribution of the sum of independently thrown dice with known probabilities.] Also basic changes of variable, and going from Σ_na_nxⁿ to Σ_nna_nxⁿ by differentiating with respect to x followed by multiplication by x (so sometimes a generating-function solution requires solving a differential equation!). The generating function for (1+x)^α for arbitrary exponent α, via Taylor's formula: if A(x)=Σ_na_nxⁿ then a_n is 1/n! times the value at x=0 of the nth derivative of A. For A(x)=(1+x)^α, we find that again a_n is Binomial(α, n) --- but we need to be careful interpreting this when α is not a natural number. This actually arises in practice: using generating functions we find that the nth Catalan number is (-1)ⁿ 2²ⁿ⁺¹ Binomial(1/2, n+1), but that still takes a bit of work to identify with the more familiar  Binomial(2n, n) / (n+1)...

November 2

• Presentations of solutions to problems from last week:
  • Fibonacci-like sequences with a(n+1) = a(n-1) + k a(n) for some constant k: (-1)ⁿ [a(n)² - a(n-1)a(n+1)] is still constant. The bracketed expression is also a(n)² - k a(n-1) a(n) - a(n-1)²; does the sequence with a(0)=0 and a(1)=1 account for all solutions of y²-kxy-x² as was the case for the Fibonacci sequence (k=1)? What other Fibonacci properties (such as the formula for F_n) generalize? What happens for a more general recursion like a(n+1) = k a(n-1) + k' a(n), or so-called Tribonacci sequences each of whose terms is the sum of the previous three?
  • Proof that our formula (-1)ⁿ 2²ⁿ⁺¹ Binomial(1/2, n+1), for the n-th Catalan number agrees with the canonical Binomial(2n, n) / (n+1) -- unexpectedly by induction, so also show the more standard approach via 1 · 3 · 5 · · · (2n-1) = (1 · 2 · 3 · 4 · 5 · 6 · · · (2n-1) · (2n)) / (2 · 4 · 6 · · · 2n) = (2n)! / (2ⁿ n!) [and be careful to distinguish "(2n)!" from "2n!" = 2·n!].
  • Problem 5: the generating function for partial sums, a.k.a. convolution with (1,1,1,...); and application to the "hockey stick" identity, again with an unexpected concluding induction, using the Pascal recursion for binomial coefficients rather than the binomial expansion of (1-x)^-(k+1).
  • Problem 6: Partial fraction decomposition of 1/(1-x-x²), and the closed form for Fibonacci (though the solvers used not the generating function but the fact that any Fibonacci recursion yields a(n)=F_n-1a(0)+F_na(1), together with the fact that a(n)=rⁿ works if r is the Golden Ratio or its conjugate, to find F(n) by solving simultaneous linear equations!)
• Introduction to convexity, via problems of maximizing perimeter or area of n-gon inscribed in a given circle, or volume of box or open box with given surface area. Jensen's inequality; further applications: AM-GM inequality (arithmetic mean ≥ geometric mean) via convexity of logarithm; special cases: Jensen for x² and 1/x are familiar consequences of Cauchy-Schwarz; answer of open-box problem suggests reflection trick to reduce to closed-box problem; a hint of the importance for compactness: what's the maximal volume enclosed by a "fence" (box without both the top and the bottom faces) of given area?...

November 9

• Presentations of solutions to problems from last week: 9; 8 (except for equality condition, via convexity of the square root rather than the expected Cauchy-Schwarz); and most of 4.
• Some applications of the Dirichlet Box (a.k.a. Pigeonhole) Principle:
  • If gcd(p,q)=1 then the fractions a/p, b/q interleave perfectly with the fractions c/(p+q) (a finite version of Beatty's Theorem -- to see the connection, multiply by p+q and let r=(p+q)/p, s=(p+q)/q)
  • There exists x such that b|mx-1 iff gcd(m,b)=1 (the "if" direction is the harder one, proved by showing that in fact b|mx-c has a unique solution with 0≤x<b for each c);
  • Existence of a “Garden of Eden” in Conway's Game of Life (WAY bigger than the small examples shown here, which were themselves improved only a few years ago)
  • Introduction to Ramsey theory, which is a canonical application of the Principle

November 16

• Report on the weekend's progress on the Erdös problem concerning sum-distinct sets, and comparisons with the previous literature.
• Geometry using Cartesian coordinates, vectors, barycentric coordinates, and complex numbers: centroid (A+B+C)/3 of triangle ABC trisects its medians ; van Aubel's theorem (cf. “Napoleon's theorem” --- can you formulate the proof outlined in the Wikipage in terms of complex numbers?); cis(θ) = cos(θ)+i sin(θ) = e^iθ, and a bit about complex roots of unity