# show this $t_{n+p^{2p}-1} \equiv t_n \pmod{p}$ with hard problem

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

• 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. – user277182 Jun 2 at 5:32

## 1 Answer

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.

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