# The number of partitions of $n$ and the $n$th Fibonacci number.

I'm very sorry if this is a duplicate in any way. There's a lot of material out there on connections between these sequences so it's a possibility . . .

Let $P_n$ be the number of partitions of $n$ and $F_n$ be the $n$th Fibonacci number.

I've been learning how to use GAP. Naturally, the accompanying tutorial gives a few examples of its use and a couple of very basic ones are functions to determine $P_n$ and $F_n$ for a given $n\in\mathbb{N}$. So I played around with them and soon I noticed $(P_{10} \operatorname{mod} F_{10}) = P_{10}$ and asked the following question.

Question 1 For which $n$ does $$(P_n \operatorname{mod} F_n) = P_n$$ (i.e., $0 \le P_n < F_n$)?

Based on what I've seen, I think it's for all $n>8$ (because it looks like $P_n<F_n$ in that case). Thus I have two more questions:

Question 2: What's so special about $9$ in this context?

and

Question 3: Is it true that $P_n<F_n$ for all $n>8$?

I'm not sure how to approach these.

NB: I hope it's clear that, a priori, Question 2 and Question 3 could be considered separate from one another (so this question won't be so stupid if the answer to Question 3 is well-known & trivial).]

• What do you mean by $a=a \pmod{b}$? Isn't it always true? – Vladimir Jul 12 '14 at 20:52
• @Vladimir Well, of course; sorry. I've edited the question accordingly. (I thought my intended meaning was obvious.) – Shaun Jul 12 '14 at 20:57
• [There's a difference between $a\equiv a \pmod{b}$ and $a=a\pmod{b}$.] – Shaun Jul 12 '14 at 21:01
• The main difference would seem to be that the first is correct notation and the second is meaningless. When $\operatorname{mod}$ is used as an infix function from $\mathbb{Z}\times\mathbb{N}^+$ to $\mathbb{N}$ you shouldn't separate it from its first argument. $(P_n \operatorname{mod} F_n) = P_n$ looks like a bizarre way of writing $0 \le P_n < F_n$, but $P_n = P_n \pmod{F_n}$ just looks like a tautology with a typo of $=$ for $\equiv$. – Peter Taylor Jul 12 '14 at 21:30
• Thank you, @PeterTaylor. Would you correct my notation with an edit, please? I'm on my phone right now so it's rather fiddly :) – Shaun Jul 12 '14 at 21:39

## 1 Answer

The partition function is asymptotically $\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{2n/3}}$ and the Fibonacci numbers are asymptotically $\frac{1}{\sqrt{5}}\varphi^n$, where $\varphi$ is the golden ratio. The quotient of these two is less than $1$ if $n$ is large enough: $$\frac{\sqrt{5}e^{\pi\sqrt{2n/3}}}{4n\sqrt{3}\varphi^n} = \frac{\sqrt{5}}{4\sqrt{3}}\cdot\frac{\left(e^{\pi\sqrt{2/3}}\right)^{\sqrt{n}}}{n\varphi^n}.$$ So $P_n < F_n$ for large enough $n$.

• This is certainly relevant, so thank you. How does it answer my questions though? – Shaun Jul 12 '14 at 21:26
• @Shaun Yes, you're right, it's not directly applicable. But it does at least show that $P_n<F_n$ for all $n$ greater than some fixed number. – rogerl Jul 12 '14 at 21:34
• I can't bring myself to accept it (yet), I'm afraid. I'm sorry. Nevertheless, you're right and it's a beautiful observation. Would you consider changing it to a comment? :) – Shaun Jul 12 '14 at 21:51
• I don't blame you. I wouldn't accept it either. I do find it hard to believe that you're going to get an answer that explains why 9 is special, though. It just is. What is interesting to me is that once $P_n<F_n$, it is $<$ forever. – rogerl Jul 12 '14 at 21:55