We define the Fibonacci sequence $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the Stirling number of the second kind $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets. For every positive integer $n$, let $$t_n = \sum_{k=1}^{n} S(n,k) F_k$$ Let $p\ge7$ be a prime. Prove that $$ t_{n+p^{2p}-1} \equiv t_n \pmod{p} $$ for all $n\ge1$.

some My try: first note that the following identity holds: $\sum_{n \ge 0}S(n, k)x^n = x^k\prod_{r = 1}^k\frac{1}{1-rx}$. So $$T(x) = \sum_{n \ge 0}t_nx^n = \sum_{n \ge 0} \sum_{k \ge 0}S(n,k) F_k x^n = \sum_{k \ge 0} \sum_{n \ge 0}S(n,k) F_k x^n = \sum_{k \ge 0} F_kx^k \prod_{r = 1}^k\frac{1}{1-rx} $$ Then I can't,Thanks

  • 1
    $\begingroup$ What is the origin of this problem? That might shed light on whether a generating function approach or a combinatorial approach is more likely to work. $\endgroup$ – user277182 Jun 2 at 5:32

Your sequence is A263576 in OEIS. Since the Fibonacci numbers have the following closed form:
$$F_n=\frac{\phi^n-(1-\phi)^{n}}{\sqrt{5}}$$ We must have: $$t_n = \sum_{k=1}^{n} S(n,k) F_k = \sum_{k=1}^{n} S(n,k)\frac{\phi^k-(1-\phi)^{k}}{\sqrt{5}}\\ = \frac{1}{\sqrt{5}}\sum_{k=1}^{n} S(n,k)\phi^k - \frac{1}{\sqrt{5}}\sum_{k=1}^{n} S(n,k)(1-\phi)^k=\frac{B_n(\phi)-B_n(1-\phi)}{\sqrt{5}}$$ Where $$B_n(x)=\sum_{k=1}^{n} S(n,k) x^k$$ Is the $n$-th Bell polynomial. Now, by Proposition 3.1. of this paper: http://www.kurims.kyoto-u.ac.jp/EMIS/journals/BBMS/Bulletin/bul964/Robert-Gertsch.pdf we obtain:
$$B_{n+p^{2p}-1}(x) \equiv B_n(x)+(x^p+x^{p^2}+...+x^{p^{2p}})B_n(x) \equiv B_n(x)+(x+...+x)B_n(x) \equiv B_n(x) \pmod{p}$$ So by the formula above we naturally get the result. However for this to work it seems that $\sqrt{5}$ needs to exist mod $p$ which happens only if $p \equiv 1$, $4 \pmod{5}$. There is probably some way to make it work for $p \equiv 2$, $3 \pmod{5}$ I just don't see how.
An alternative approach would be to make use of Corollary 2.2 from http://matwbn.icm.edu.pl/ksiazki/aa/aa94/aa9413.pdf and known behavior of Fibonacci numbers mod $p$ but I haven't been able to make it work either.

  • 1
    $\begingroup$ If $\sqrt5$ does not exist modulo $p$, we can still adjoin it to $\mathbb{F}_p$, or am I misreading you? $\endgroup$ – darij grinberg Jun 9 at 13:58
  • $\begingroup$ Of course we can, that solves the problem completely. Thank you. $\endgroup$ – Bartek Jun 9 at 14:49

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.