A student asked me the other day the following rather homework-looking question: Given a natural number , how many solutions does the equation

have for and natural numbers?

The question has a very easy answer: Simply notice that and that any like this determines a unique such that is a solution. So, there are solutions if is even (as can be any of ), and there are solutions if is odd.

I didn’t tell the student what the answer is, but I asked what he had tried so far. Among what he showed me there was a piece of paper in which somebody else had scribbled

which caught my interest, and is the reason for this posting.

I don’t think the student had seen the connection between this product of two series, let’s call it , and his question. If we denote by the number of solutions to the equation, the series is the generating function of the sequence , i.e.,

To see this, notice that the coefficient of in is precisely the number of ways we can write as a product of a term from the first series and a term from the second one, i.e., it is the number of solutions with and natural numbers to the equation or, equivalently, . That is to say, the coefficient of in is exactly .

This gives us a purely algebraic (analytic?) way of solving the question, even if there is no understanding of how to approach it from a combinatorial point of view.

Both series on the product that makes up are geometric series, so we have

that of course coincides with the formula we obtained earlier by combinatorial considerations.

The question the student had is a very simple example of a problem about integer partitions, a beautiful area of mathematics that I hope I am not misconstruing by thinking of as a branch of combinatorial number theory. The technique of generating functions is a very useful and powerful combinatorial tool that I have always found quite nice although, granted, its use is a bit of an overkill for the question at hand. At the same time, this technique provides us with a (standard) method for solving any problem of the same kind: For fixed natural numbers , find for each the number of tuples of natural numbers such that

One can then go further to study the much subtler partition function and its relatives.

(And I still don’t know the name of the student, who didn’t bother to introduce himself, and I have no idea who suggested to him to look at to begin with.)

Well, I got the partial solution finally, here is the question that I tried to solve by the equation x + 2y = n, x,y,n > 0

Let n be a positive integer. Harry’s school year has n school days. Harry has budget of exactly $n for buying exactly one snack per day at school. There are only two types of snacks available: M&M for $1. 00 per packet, or a pair of bananas at $2.00 per pair. The following restrictions must apply to Harry.

(1) Harry must spend all $n on snacks during the school year.

(2) Harry does not have to buy a snack each school day.

At the end of the school year, Harry must report how many times he bought M&M, and how many times he bought bananas. How many different reports are possible?

Anyway, thank you for your posting 🙂 It helps me to understand the solution better.

This is a very interesting question (and I really want to see what other answers you receive). I do not know of any general metatheorems ensuring that what you ask (in particular, about consistency strength) is the case, at least under reasonable conditions. However, arguments establishing the proof theoretic ordinal of a theory $T$ usually entail this. You […]

This is false; take a look at https://en.wikipedia.org/wiki/Analytic_set for a quick introduction. For details, look at Kechris's book on Classical Descriptive Set Theory. There you will find also some information on the history of this result, how it was originally thought to be true, and how the discovery of counterexamples led to the creation of desc […]

This is open. In $L(\mathbb R)$ the answer is yes. Hugh has several proofs of this, and it remains one of the few unpublished results in the area. The latest version of the statement (that I know of) is the claim in your parenthetical remark at the end. This gives determinacy in $L(\mathbb R)$ using, for example, a reflection argument. (I mentioned this a wh […]

A classical reference is Hypothèse du Continu by Waclaw Sierpiński (1934), available through the Virtual Library of Science as part of the series Mathematical Monographs of the Institute of Mathematics of the Polish Academy of Sciences. Sierpiński discusses equivalences and consequences. The statements covered include examples from set theory, combinatorics, […]

There is a new journal of the European Mathematical Society that seems perfect for these articles: EMS Surveys in Mathematical Sciences. The description at the link reads: The EMS Surveys in Mathematical Sciences is dedicated to publishing authoritative surveys and high-level expositions in all areas of mathematical sciences. It is a peer-reviewed periodical […]

You may be interested in the following paper: Lorenz Halbeisen, and Norbert Hungerbühler. The cardinality of Hamel bases of Banach spaces, East-West Journal of Mathematics, 2, (2000) 153-159. There, Lorenz and Norbert prove a few results about the size of Hamel bases of arbitrary infinite dimensional Banach spaces. In particular, they show: Lemma 3.4. If $K\ […]

You just need to show that $\sum_{\alpha\in F}\alpha^k=0$ for $k=0,1,\dots,q-2$. This is clear for $k=0$ (understanding $0^0$ as $1$). But $\alpha^q-\alpha=0$ for all $\alpha$ so $\alpha^{q-1}-1=0$ for all $\alpha\ne0$, and the result follows from the Newton identities.

Nice question. Let me first point out that the Riemann Hypothesis and $\mathsf{P}$-vs-$\mathsf{NP}$ are much simpler than $\Pi^1_2$: The former is $\Pi^0_1$, see this MO question, and the assertion that $\mathsf{P}=\mathsf{NP}$ is a $\Pi^0_2$ statement ("for every code for a machine of such and such kind there is a code for a machine of such other kind […]

For brevity's sake, say that a theory $T$ is nice if $T$ is a consistent theory that can interpret Peano Arithmetic and admits a recursively enumerable set of axioms. For any such $T$, the statement "$T$ is consistent" can be coded as an arithmetic statement (saying that no number codes a proof of a contradiction from the axioms of $T$). What […]

I’m the student asked the question 😉

Well, I got the partial solution finally, here is the question that I tried to solve by the equation x + 2y = n, x,y,n > 0

Let n be a positive integer. Harry’s school year has n school days. Harry has budget of exactly $n for buying exactly one snack per day at school. There are only two types of snacks available: M&M for $1. 00 per packet, or a pair of bananas at $2.00 per pair. The following restrictions must apply to Harry.

(1) Harry must spend all $n on snacks during the school year.

(2) Harry does not have to buy a snack each school day.

At the end of the school year, Harry must report how many times he bought M&M, and how many times he bought bananas. How many different reports are possible?

Anyway, thank you for your posting 🙂 It helps me to understand the solution better.

Hi Eliot,

I’m glad this helped. Marion mentioned to me the `M&Ms problem’ the other day, I figured this was the same question without distractions.