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?


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).]

  • 3
    $\begingroup$ What do you mean by $a=a \pmod{b}$? Isn't it always true? $\endgroup$ – Vladimir Jul 12 '14 at 20:52
  • $\begingroup$ @Vladimir Well, of course; sorry. I've edited the question accordingly. (I thought my intended meaning was obvious.) $\endgroup$ – Shaun Jul 12 '14 at 20:57
  • 1
    $\begingroup$ [There's a difference between $a\equiv a \pmod{b}$ and $a=a\pmod{b}$.] $\endgroup$ – Shaun Jul 12 '14 at 21:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – Peter Taylor Jul 12 '14 at 21:30
  • $\begingroup$ Thank you, @PeterTaylor. Would you correct my notation with an edit, please? I'm on my phone right now so it's rather fiddly :) $\endgroup$ – Shaun Jul 12 '14 at 21:39

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$.

| cite | improve this answer | |
  • $\begingroup$ This is certainly relevant, so thank you. How does it answer my questions though? $\endgroup$ – Shaun Jul 12 '14 at 21:26
  • 1
    $\begingroup$ @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. $\endgroup$ – rogerl Jul 12 '14 at 21:34
  • $\begingroup$ 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? :) $\endgroup$ – Shaun Jul 12 '14 at 21:51
  • $\begingroup$ 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. $\endgroup$ – rogerl Jul 12 '14 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.