Partition Function and Fibonacci Number

Question

I am asked to prove that $$p(n) < F_n, \qquad n \geq 5$$ where $p(n), \ F_n$ are the number number of partitions of $n$ and the $n^{th}$ Fibonacci number, respectively. This is easy if you can show that $$p(n) \leq p(n - 1) + p(n - 2)$$ I am trying to use the recurrence relation for $p(n)$, but haven't been able to show $p(n) \leq p(n - 1) + p(n - 2)$. Does anyone have any insight for showing this with the recurrence relation?

Answer 1

Let $P_k(n)$ be the number of partitions of $n$ into $k$ parts.

If a partition counted in $P_k(n)$ contains no $1$s then subtracting $1$ from every number gives a partition which is counted in $P_k(n-k)$.

If a partition counted in $P_k(n)$ contains at least one $1$ then deleting a $1$ gives a partition which is counted in $P_{k-1}(n-1)$.

Therefore $$P_k(n)= P_k(n-k)+P_{k-1}(n-1).$$ For $k=1$, $P_1(n)= P_1(n-2)=1$ and for $k\ge2$, $P_k(n)\le P_k(n-2)+P_{k-1}(n-1)$.

So, if we sum over all $k$, we obtain $$P(n)\le P(n-2)+P(n-1),$$ as required.