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$. Proposed by Victor Wang
Problem
Source: ELMO Shortlist 2013: Problem N8, by Victor Wang
Tags: counting, distinguishability, modular arithmetic, algebra, polynomial, function, number theory unsolved
11.11.2013 22:07
12.11.2013 00:46
mathocean97 wrote: For some reason, I couldn't find an easier way to show the divisibility, maybe someone can help me?
22.11.2014 16:56
mathocean97 wrote: Anyways, so 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}$ Why is this identity true and how did you come up with this? Is it well known?
29.11.2014 01:58
MathPanda1 wrote: mathocean97 wrote: Anyways, so 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}$ Why is this identity true and how did you come up with this? Is it well known? Yes, it is a rather well-known generating functions identity for the Stirling numbers. It's even on Wikipedia! It's probably a good generating functions exercise to prove this: you can either use the recurrence relation or the explicit form.
29.11.2014 02:11
May I ask, was it difficult to come up with your beautiful proof? What are some inspirations for coming up with this proof?
04.12.2014 00:11
MathPanda1 wrote: May I ask, was it difficult to come up with your beautiful proof? What are some inspirations for coming up with this proof? I guess why I decided to use generating functions here was because the way $t_n$ was defined, as the sum of the product of 2 sequences, made it nice to use generating functions on. Afterwards, it was just manipulations of polynomials over finite fields (specifically $\mathbb{F}_{p^2}$), which I've done before.
05.12.2014 14:45
mathocean97 wrote: So we can finish by showing that in $\mathbb{F}_{p^2}$, $T(x) \cdot \left(x^{p^{2p}-1}-1 \right)$ is a polynomial (that would mean that all $x^n, x^{n+p^{2p}-1}$ terms would have to cancel each other out, so we'd be done). Why does this imply the result for all $n \ge 1$? I can only see why it implies $t_{N+p^{2p}-1} \equiv t_N \pmod p$ for all sufficiently large $n$. Thanks.
05.12.2014 22:59
v_Enhance wrote: Why does this imply the result for all $n \ge 1$? I can only see why it implies $t_{N+p^{2p}-1} \equiv t_N \pmod p$ for all sufficiently large $n$. Thanks. Sorry, your objection is correct. Luckily, this can be patched easily, because I computed that \[ T(x) = \frac{1}{\sqrt{5}}\sum_{k = 0}^{p-1}S\prod_{r = 1}^k\frac{1}{1-rx}\left(\frac{(\alpha x)^k}{1-x^{p-1}-\alpha^p x^p}-\frac{(\beta x)^k}{1-x^{p-1}-\beta^p x^p}\right). \] By looking at each term of the above sum, we see that $T(x) \cdot (x^{p^{2p}-1}-1)$ has degree at most $p^{2p}-1$, since each term in the sum for $T(x)$ has "degree" 0. (Degree of numerator minus degree of denominator is 0). Since the degree of our resulting polynomial is at most $p^{2p}-1$, the $t_nx^n$ and $t_{n+p^{2p}-1}x^{n+p^{2p}-1}$ terms must cancel for any $n \ge 1$.
07.12.2014 08:49
I'd just like to point out that there is a somewhat related problem (though much easier); namely, that $F_{n+p^2-1} \equiv F_{n} \pmod{p}$ for prime $p \neq 2, 5$. This follows from the fact that \[ \alpha ^ {p^2-1} = \alpha ^ {p^2} \beta = \frac{1 + (\sqrt{5})^{p^2}}{2} \beta = \frac{1 + (5^{p-1})^{p+1/2} \cdot \sqrt{5}}{2}\beta = \alpha\beta = 1 \] in $\mathbb{F}_{p^2}$, and $\beta ^ {p^2-1} = 1$ which can be proved similarly. The desired result now follows easily from $F_n=\frac{\alpha ^ n - \beta ^ n}{\sqrt{5}}$.