Michael Z. Spivey
Department of Mathematics and Computer Science
University of Puget Sound
CONTENTS
- Education
- My Book
- Published Articles in Mathematics
- Unpublished Articles in Mathematics
- Other Mathematics Publications
- Non-Mathematical Publications
- Interactive Fiction
- Ph.D., operations research, Princeton University, Princeton, New Jersey, 2001.
- M.A., operations research, Princeton University, Princeton, New Jersey, 1999.
- M.S., mathematics, Texas A&M University, College Station, Texas, 1997.
- B.S., mathematics, Samford University, Birmingham, Alabama, 1994.
- High school diploma, humanities, Louisiana School for Math, Science, and the Arts, Natchitoches, Louisiana, 1991.
The Art of Proving Binomial Identities, CRC Press, 2019.
- This text describes how to use a wide variety of tools for proving identities involving the binomial coefficients: algebraic manipulation, combinatorics, calculus, probability,
generating functions, recurrence relations and finite differences, special numbers, complex numbers, linear algebra, and mechanical summation.
- List of known errors in the book.
- Some review comments:
- "I often tell my students that all mathematics is found in Pascal’s Triangle, and this book is Spivey’s attempt to verify this statement. A more detailed list of contents follows, but calculus, linear algebra, probability,
and complex analysis are all used in this delightful text... this text is well written and well organized and I am pleased that such a text exists. We only need more mathematics departments to realize that their majors need a course for
which this text could be used." — Wayne M. Dymacek, MathSciNet / Mathematical Reviews (starred review)
- "Anyone solving problems found in mathematics journals—or preparing for mathematics contests—will find this text invaluable." — J. T. Zerger, Catawba College, from CHOICE
- On the Number of Trials Needed to Obtain k Consecutive Successes, with
Steve Drekic. Statistics & Probability Letters, 176: 109132, 2021.
- We derive a new expression for the probability mass function for the number of independent Bernoulli trials needed to achieve k consecutive successes. Then we use this formula to derive closed-form
expressions for the complementary cdf and factorial moments.
- A Combinatorial View of Sums of Powers, Mathematics Magazine, 90 (2): 125-131, 2021.
- This paper gives a combinatorial interpretation of the sum of powers of the first n positive integers. Then it uses that combinatorial interpretation to prove two formulas for the power sum: one involving
Stirling numbers and one involving Eulerian numbers.
- Recurrent Combinatorial Sums and Binomial-Type Theorems, Journal of Integer Sequences, 23 (5): Article 20.5.5, 2020.
- In this paper I show that several known combinatorial sum identities (including identities for the binomial coefficients, both kinds of Stirling numbers, and Lah numbers) are all special cases of a single, more general
identity. I also derive conditions under which numbers that satisfy a general two-term recurrence satisfy a binomial-type theorem. Lastly, I give a combinatorial proof of a binomial-type theorem satisfied by the Stirling numbers
of the first kind.
- Engaging the Paradoxical: Zeno's Paradoxes in Three Works of Interactive Fiction, Journal of Humanistic Mathematics, 10 (1): 39-65, 2020.
- This paper compares and contrasts representations of Zeno's paradoxes in Beyond Zork, The Chinese Room, and my own A Beauty Cold and Austere, three works of interactive fiction.
- Mathematics Through Narrative, Math Horizons, 26 (3): 22-25, 2019.
- This short expository paper discusses mathematics in interactive fiction, with an emphasis on my own work A Beauty Cold and Austere.
- The Chu-Vandermonde Identity via Leibniz's Identity for Derivatives, College Mathematics Journal,
47 (3): 219-220, 2016. Copyright 2016 Mathematical
Association of America. All Rights Reserved.
- In this paper I derive the Chu-Vandermonde identity (usually proved via a combinatorial or a generating function argument) using Leibniz's generalized product rule for
derivatives.
- The Binomial Recurrence, Mathematics Magazine, 89 (3): 192-195, 2016. Copyright 2016 Mathematical
Association of America. All Rights Reserved.
- This paper derives the factorial formula for the binomial coefficients directly from the binomial recurrence, without assuming the formula is known in advance and only
using properties of two-variable recurrence relations.
- Probabilistic Proofs of a Binomial Identity, Its Inverse, and Generalizations, American
Mathematical Monthly, 123 (2): 175-180, 2016. Copyright 2016 Mathematical Association of America. All Rights Reserved.
- In this paper I give elementary probabilistic proofs of a binomial identity, its binomial inverse, and generalizations of both of these. The proofs are obtained by interpreting the sides of each
identity as the probability of an event in two different ways. Each proof uses a classic balls-and-jars scenario.
- Multiplicative Functions, Generalized Binomial Coefficients, and Generalized Catalan Numbers, with Tom Edgar. Journal of Integer Sequences 19 (1): Article 16.1.6, 2016.
- In this paper Tom and I derive a formula for generalized binomial coefficients (in the sense of Knuth and Wilf's classic paper) formed from
multiplicative functions. We then use this formula to prove that generalized binomial coefficients and generalized Catalan numbers are always integral when the underlying functions are both multiplicative and divisible.
- A Combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients,
American Mathematical Monthly, 121 (6): 537-540, 2014.
- We give a combinatorial proof of the identity for the alternating convolution of the central binomial coefficients. Our proof entails applying an involution to certain
colored permutations and showing that only permutations containing cycles of even length remain.
- The Lah Numbers and the nth Derivative of e1/x, with Siad Daboul, Jan Mangaldan, and Peter Taylor. Mathematics Magazine, 86 (1): 39-47,
2013.
- We give five proofs that the coefficients in the nth derivative of exp(1/x) are the Lah numbers, a triangle of integers whose best-known applications are in combinatorics and finite difference calculus.
Our proofs use tools from several areas of mathematics, including binomial coefficients, Faà di Bruno's formula, set partitions, Maclaurin series, factorial powers, the Poisson probability distribution, and hypergeometric functions. The
paper is based on the discussion to Siad's question about the nth derivative of exp(1/x) on Math Stack Exchange.
- Optimal Discounts for the Online Assignment Problem. Operations Research Letters, 41: 112-115, 2013.
- This paper proves that, for two simple functions drlt, solving the online assignment problem with crl - drlt as the contribution for assigning resource r to task
l at time t gives the optimal solution to the corresponding offline assignment problem (provided the optimal offline solution is unique). We call such functions drlt optimal discount functions.
This paper gives a simpler proof of the results in one of my dissertation papers, "Some Fixed-Point Results for the Dynamic Assignment Problem," as well as answering the
major open theoretical question from my dissertation.
- Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points. Electronic Journal of Combinatorics,
19 (3): Article P24, 2012.
- This paper gives bijective proofs that, when combined with one of the combinatorial proofs of the general ballot formula, constitute a combinatorial argument yielding the number of lattice paths from (0; 0) to
(n; rn) that touch or cross the diagonal y = rx at exactly k lattice points. The enumeration partitions all lattice paths from (0; 0) to (n; rn). While the resulting formula can be derived
using results from Niederhausen, the bijections and combinatorial proof are new.
- On Solutions to a General Combinatorial Recurrence. Journal of Integer Sequences, 14 (9): Article 11.9.7, 2011.
- This paper gives a partial solution to research problem 6.94 in Concrete Mathematics. It shows how to solve a large class of two-term combinatorial recurrence relations in terms of sums of binomial coefficients
and the two kinds of Stirling numbers. Some known combinatorial identities involving named numbers (e.g., Stirling, Eulerian, Bell) are given a more unified treatment, and some new identities are proved.
- Asymptotic Moments of the Bottleneck Assignment Problem. Mathematics of Operations Research, 36 (2): 205-226, 2011.
- In this paper we give a method by which one can find all of the asymptotic moments of a random bottleneck assignment problem in which costs (independent and identically distributed) are chosen from a wide variety of
continuous distributions. The results improve on those obtained by Pferschy in the mid-90s.
- The Poisson Process and Associated Probability Distributions on Time Scales, with Dylan Poulsen
and Robert Marks. IEEE 43rd Southeastern Symposium on System Theory (SSST): 49-54, March 2011.
- As the title indicates, this article develops the Poisson process and the related Poisson, Erlang, and exponential distributions for a general time scale. As an application, the Poisson distribution and the binomial
distribution are shown to be the same probability distribution on different time scales. (Most of this work was done by Dylan as a summer project while he was an undergraduate. He is now a professor at Washington College.)
- Cycles in War. Integers, 10: Article G2, 747-764, 2010.
- We discuss a simplified version of the well-known card game War in which the cards in the deck have a strict ranking from 1 to n and in which the winning card and losing card are immediately placed, in that
order, at the bottom of the winning player's deck. Under this variation of War we show that it is possible for a standard fifty-two card deck to cycle, and we exhibit such a cycle. This result is a special case of a more general
result that exhibits a cycle construction for an n-card deck for any value of n that is not a power of 2 or 3 times a power of 2. We also discuss results that show that under some assumptions the types of cycles we
exhibit are the only types of cycles that can occur.
- Visualising Continued Fractions. Mathematical Gazette, 94 (530): 284-290, 2010.
- This paper describes a method for visualizing finite continued fractions in terms of a grid.
- Deranged Exams. College Mathematics Journal, 41 (3): 197-202, 2010.
- This expository paper discusses a triangle of numbers Sn,k that are related to the derangement numbers. The Sn,k numbers satisfy a
Pascal-like recurrence relation with subtraction instead of addition. We describe how they relate to numbers studied by other authors and use them to generalize Euler's famous recurrence
relation for the derangement numbers.
- Staircase Rook Polynomials and Cayley's Game of Mousetrap. European Journal of Combinatorics, 30 (2): 532-539, 2009.
- We determine the rook polynomials for two special classes of card decks arising in the game of Mousetrap, introduced by Arthur Cayley 150 years ago.
- A Generalized Recurrence for Bell Numbers. Journal of Integer Sequences, 11 (2): Article 08.2.5, 2008.
- We give a combinatorial proof of a result that generalizes the two most well-known expressions for Bell numbers.
- Symmetric Polynomials, Pascal Matrices, and Stirling Matrices, with Andy Zimmer.
Linear Algebra and Its Applications, 428 (4): 1127-1134, 2008.
- We consider lower-triangular matrices consisting of symmetric polynomials, and we show how to factorize and invert them. Since binomial coefficients and Stirling numbers can be
represented in terms of symmetric polynomials, these results contain factorizations and inverses of Pascal and Stirling matrices as special cases. This work generalizes that of several other
authors on Pascal and Stirling matrices. (Andy did his part of the work as an undergraduate at the University of Puget Sound; he is now a professor at Louisiana State University.)
- Counting Functions and Finite Differences, with Natalio Guersenzvaig. Integers, 7: Article A59, 2007.
- Any increasing function p(d) on the natural numbers has an associated counting function pi(n) that yields the number of inputs d for which p(d) <=
n. In this article we derive three formulas that relate a sequence to its finite difference sequence by way of counting functions and the technique of summation by parts. We demonstrate
our formulas by using them to produce several identities for Fibonacci numbers and binomial coefficients.
- Combinatorial Sums and Finite Differences. Discrete Mathematics, 307 (24): 3130-3146, 2007.
- This paper shows how the binomial transform of
a sequence is related to the binomial transform of the finite difference of the sequence. This relationship can be used to give fairly quick derivations of some known binomial sum identities.
The approach is then modified so that it applies to alternating binomial sums, aerated binomial sums, and to sums involving signed and unsigned Stirling numbers of the first kind. The paper
concludes with a generalization of the results for binomial sums and unsigned Stirling numbers of the first kind.
- Quadratic Residues and the Frobenius Coin Problem. Mathematics Magazine, 80 (1): 64-67, 2007.
- An odd prime p has (p-1)/2 quadratic residues mod p, and for relatively prime p and q there are (p-1)(q-1)/2 non-representable
Frobenius numbers. We show that there is a relationship between the non-representable Frobenius numbers of p and q and the quadratic residues of p that accounts for the
presence of (p-1)/2 in both expressions.
- Fibonacci Identities via the Determinant Sum Property. College Mathematics Journal, 37 (4): 286-289, 2006.
- We use the sum property for determinants of matrices to give a three-stage proof of an identity involving Fibonacci numbers. Cassini's and d'Ocagne's Fibonacci identities are obtained at the
ends of stages one and two, respectively. Catalan's Fibonacci identity is also a special case.
- Some Inversion Formulas for Sums of Quotients, with Natalio Guersenzvaig. Crux Mathematicorum, 32 (1): 39-43, 2006.
- This paper proves some identities related to summing the quotients of an integer n from two different directions. The results generalize a problem posed in a previous issue
of Crux.
- The Euler-Maclaurin Formula and Sums of Powers. Mathematics Magazine, 79 (1): 61-65, 2006.
- This paper uses the Euler-Maclaurin formula for approximating a sum by an integral to prove that the limiting value of a certain expression related to the power sum is 1/(e-1).
- See also my letter to the editor, Mathematics Magazine, 83 (1): 54-55, 2010.
- The k-Binomial Transforms and the Hankel Transform, with Laura Steil.
Journal of Integer Sequences, 9 (1): Article 06.1.1, 2006.
- We give a new proof of the invariance of the Hankel transform under the binomial transform of a sequence. Our method of proof leads to three variations of the binomial transform;
we call these the k-binomial transforms. We give a simple means of constructing these transforms via a triangle of numbers. We show how the exponential generating function of a sequence
changes after our transforms are applied, and we use this to prove that several sequences in the On-Line Encyclopedia of Integer Sequences are related via our transforms. In the process,
we prove three conjectures in the OEIS. Addressing a question of Layman, we then show that the Hankel transform of a sequence is invariant under one of our transforms, and we show how the
Hankel transform changes after the other two transforms are applied. Finally, we use these results to determine the Hankel transforms of several integer sequences. (This is an extension of
Laura's undergraduate senior thesis; she is now a professor at Mars Hill College in North Carolina.)
- The Humble Sum of Remainders Function. Mathematics Magazine, 78 (4): 300-305, 2005.
- Given an integer n, define the sum of remainders function such that when n is input to the function, the output is the sum of the the remainders obtained by dividing
n successively by 1, 2, ..., n. This paper describes two uses of the sum of remainders function: 1) It provides a simple alternative characterization of perfect numbers, and
2) together with the more famous sum of divisors function, it helps give an expression for the sums of powers of the first n positive integers.
- The Dynamic Assignment Problem, with Warren Powell. Transportation Science, 38 (4): 399-419, 2004. (c)
Informs
- In this paper we introduce the dynamic assignment problem, which involves the solution of assignment problems over time with evolving information on the availability of resources and tasks, contributions
for assigning them, and restrictions on the availability of assignments. The paper includes 1) a formal model of the problem, 2) an adaptive approximation strategy for problems with relatively small state
spaces based on the values of resources, tasks, and resource-task pairs that significantly outperforms greedy heuristics, and 3) an extension of this strategy, based on aggregations of
resources and tasks, to problems with larger state spaces. (This paper represents the bulk of the work from my Ph. D. dissertation.)
- Some Fixed-Point Results for the Dynamic Assignment Problem, with Warren Powell. Annals of Operations
Research, 124: 15-33, 2003.
- In the process of testing the adaptive approximation algorithm described in the following paper, we discovered that for certain problem classes, when the optimal solution is input to our
algorithm, the algorithm outputs the optimal solution in the next iteration. This means that the optimal solution is a fixed point under our algorithm for these problem classes. This paper
contains the proofs of this for two of these classes (provided the optimal solution is unique).
- A Narrow Margin, my math blog, with over 100 posts from 2011 to the present
- "A Product Calculus." This paper describes an alternate form of calculus, one in which multiplication plays the role that addition does in the usual calculus. This
kind of calculus is not new, but it was not very well-known, and the purpose of my paper was to advertise it. The paper was first written in the summer of 2006. I tried for a few years to have it published and was unsuccessful. In
the intervening years other authors published articles describing the same kind of calculus, it has become more well-known, and I have decided it is not worth my while to continue to try to publish my version. I offer it here for
anyone who is interested. For more information, see the Wikipedia article on multiplicative calculus.
- "L'Hôpital's Rules and Taylor's Theorem for Product Calculus," with Alex Twist. This paper is a follow-up to my product calculus paper. Most of the work was
done by my student Alex during the summer of 2007.
- Solution to Problem 2826, with P. Bornsztein, et al. Crux Mathematicorum, 30 (3): 178-179, April 2004.
- Solution to Problem 2834, with C. Curtis. Crux Mathematicorum, 30 (3): 186, April 2004.
- Solution to Problem 1, 32nd Austrian Mathematics Olympiad, Crux Mathematicorum, 31 (6): 376, October 2005.
- Problem 1737, Mathematics Magazine, 79 (1): 67, February 2006. Also, see the discussion of this problem at Cut-the-Knot.
- Letter to the editor, Mathematics Magazine, 83 (1): 54-55, 2010. (This letter contains some comments on - including the correction to a mistake in - my paper
"The Euler-Maclaurin Formula and Sums of Powers" that appeared in the February 2006 issue of Mathematics Magazine.)
- Dialing Back the Rhetoric, Inside Higher Ed, December 8, 2016. This article describes my experiences
giving the "conservative" perspective on a panel the day after Donald Trump's 2016 election as president of the United States.
- A Beauty Cold and Austere, a text-based game that explores mathematical ideas and the history of mathematics.
- Junior Arithmancer, another text-based mathy game, with more focus on puzzles and less focus on narrative than ABCA.
- 7th place (out of 77 games), 2018 Interactive Fiction Competition
- 2nd place, Miss Congeniality (a ranking of games based on the authors' votes), 2018 Interactive Fiction Competition
- Winner, Best Puzzles, 2018 XYZZY Awards for interactive fiction
- Nominee, Best Implementation, 2018 XYZZY Awards
- Sugarlawn, the traveling salesman problem with pickup and delivery in the form of an interactive fiction-style treasure hunt.
- 4th place (out of 82 games), 2019 Interactive Fiction Competition
- Winner, Miss Congeniality (a ranking of games based on the authors' votes), 2019 Interactive Fiction Competition
- Nominee, Best Puzzles, 2019 XYZZY Awards for interactive fiction
- Nominee, Best Implementation, 2019 XYZZY Awards
- Cragne Manor, a tribute to the classic interactive fiction work Anchorhead, written by
84 different authors.
- Winner, Best Implementation, 2018 XYZZY Awards for interactive fiction
- Nominee, Best Game, 2018 XYZZY Awards
- Nominee, Best Use of Innovation, 2018 XYZZY Awards