Partition Identity Proof

Question

Hey guys I am trying to prove the following inequality.

Prove that $p(n)\leq p(n-1)+p(n-2)$ for every $n \geq 1$. Here, $p(m)$ denotes the number of partitions of $m$.

I worked on breaking it down into steps. I think that the best way to go about with this is in steps by considering:

(a) the number of partitions $n$ that have at least two parts equal to 1.

(b) then the other partitions.

Answer 1

As requested, I'll solve part (a) here. For completeness I'm including my comments above.

A bijection is a map from one set to another that is both one-to-one and onto (maps to each element in the target set exactly once). A bijection preserved cardinality (by definition), so if we have a bijection between the two sets, they have the same number of things in them. In this case, our first set is "partitions of n with a part equal to 1" and our second set is "partitions of n-1". Now, if we delete that part equal to 1, we get a partition of n-1, right? Or if we added it back, we'd have a partition of n with a part equal to 1. So this definitely defines a map; try to show it's bijective by showing it's one-to-one and onto.

For onto, consider a partition of $n-1$: say it's $\lambda_1 + \lambda_2 + ... + \lambda_k = n-1$. But then $\lambda_1 + \lambda_2 + ... + \lambda_k + 1$ is a partition of $n$ that has a part equal to one, and deleting that part equal to one sends us to the first partition. Since that partition of $n-1$ was arbitrary, every partition of $n-1$ is mapped to.

For one-to-one, imagine some partition of $n-1$ is mapped to by two different partitions of $n$ that have a part equal to one. But this obviously can't happen - all our map does is delete a single part (equal to $1$), so we can un-do it by adding a part equal to $1$. And adding a part equal to $1$ can't give us two different partitions. So nothing is mapped to more than once.

Answer 2

Here's a fairly straightforward injection from partitions of $n$ to partitions of $n-1$ and $n-2$.

Let $\lambda_1+\lambda_2+\cdots+\lambda_k$ with $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_k\ge1$ be a partition of $n$ into $k$ parts. If $\lambda_k=1$, then we have $\lambda_1+\lambda_2+\cdots+\lambda_{k-1}$ as a partition of $n-1$ into $k-1$ parts. If $\lambda_k\gt1$ and $k\gt1$, then we have $\lambda_1+\lambda_2+\cdots+(\lambda_{k-1}-1)+(\lambda_k-1)$ as a partition of $n-2$ into $k$ parts. Finally, if $k=1$, then we have $\lambda_1-2$ as a partition of $n-2$ into $k$ parts.

As it happens, this injection gives all partitions of $n-1$ but (in general, i.e., for $n\gt4$) only some partitions of $n-2$. The key thing to note is that the mapping I've described truly is an injection -- that is, you don't get the same partition of $n-1$ or $n-2$ from two different partitions of $n$.