Combinatorial approach to prove divisibility results with the sequence $u_{n+p+1} = u_{n+p} + u_{n}$ in $\mathbb{F}_p$

Question

For a fixed prime number $p$, we consider the sequence : $$\left\{ \begin{array}{l} u_n = 1, & 0\leq n \leq p \\ u_{n+p+1} = u_{n+p} + u_n \end{array}\right. $$ I want to prove that $\forall a \in \mathbb{N},\ p|u_{pa}-u_a$

My attempt :

I think that there are two natural approaches to tackle this problem:

• One way is to apply results about linear sequences, but i'm not very familiar with how it should be done in the field $\mathbb{F}_p$. We thus consider the characteristic polynomial $Q(X) := X^{p+1}-X^p-1$ in the field $\mathbb{F}_p$. One can easily check that $Q'(X) = X^p$ and has only $0$ as a root, which is not a root of $Q(X)$, thus every roots of $Q(X)$ are simple.

If we could say that $u_n = \sum_{k} \lambda_k\alpha_k^n$ with $\alpha_k$ roots of $Q(X)$, then we would be done by Fermat's theorem.

My problem is that I think that $Q(X)$ has at most $2$ roots, that are those of $X^2-X-1$ (and actually we would need that $5$ is a square $mod(p)$, ie. that $p$ must be either $1\ mod(5)$ or $-1\ mod(5)$ by quadratic reciprocity)

• The second approach is more combinatorial, and use the fact that $u_n$ can be interpreted as the number of ways one can tile a $(p+1)\times n$ rectangle with $(p+1)\times 1$ dominos. Indeed the relationship can be derived by observing that a $(p+1)\times(n+p+1)$ tiling is either a $(p+1)\times(n+p)$ tiling with a vertical domino filing the last slice, or a $(p+1)\times n$ tiling with $(p+1)$ horizontal domino filing the remaining square.

If we consider a $(p+1)\times pa$ rectangle, then we can "naturally" slice it in $p$ rectangles of size $(p+1)\times a$. There are $u_a^p$ ways of tiling the initial rectangle with dominos that doesn't "cut" a small rectangle. By Fermat's theorem, we need to show that the number of tilings $v_{pa}$ having a domino that "cut" a small rectangle is a multiple of $p$, because we would have $u_{pa} = u_a^p + v_{pa} = u_a\ mod(p)$.

I don't know how to show this. The ideal proof would be to find an action splitting the possible tilings into $p$ orbits of the same size for example. I also tried to explicit $v_{bp}$ with the inclusion-exclusion principle (but I assumed $a\geq 2p$ so that's not very satisfying):

If we note the inner vertical edges of the small rectangles from left to right by $1,\dots,p-1$ we can try to split by the events $A_j = \{ \text{tilings with a domino cuting the edge}\ j\}$ and I found, if not mistaken: $$ v_{pa} = \sum_{k=1}^{p-1}(-1)^{k-1}\sum_{1\leq i_1 \leq \dots \leq i_k \leq p-1}\ \sum_{n^k \in \{1,\dots,p\}^k}\ \prod_{j=1}^{k+1}(u_{i_j a - (p+1-n_{j-1}^k+n_j^k)}) $$ with the boundary conditions $i_{k+1} = p-\sum_{j=0}^k i_j$ and $n_0^k = n_{k+1}^k = 0$, but I'm not sure we can make something out of it.

Because I haven't got a proof of this result, anything would be welcomed but I'm particularly curious about where the combinatorial approach would lead as it seems more elementary.

Answer 1

For the sake of completeness, I would like to propose additional solutions to the problem, that should be a little bit more elementary in the sense that they don't require extension fields of $\mathbb{F}_p$.

We will use a slightly different combinatorial interpretation of the sequence: for all $n\in \mathbb{N}$, $u_n$ is the number of possible tilings of a $1\times n$ rectangle using $1\times 1$ dominos and $1\times (p+1)$ dominos (simply consider a horizontal slice of the $(p+1)\times n$ rectangle). Using this interpretation, we will refer to the $1\times 1$ dominos as the "short" dominos and the $1\times (p+1)$ dominos as the "long" dominos.

• First proof (based on arithmetic identities):

The idea is that we can derive the following closed form of $u_n$ : $$ u_n = \sum_{k\geq 0} \binom{n-pk}{k} $$ assuming that $\binom{n}{k} = 0$ whenever $k > n$. This can be proved with the combinatorial interpretation in the following way:

Partition the set of possible tilings of a $1 \times n$ rectangle according to the number of long dominos a tiling is using. Let $k \in \mathbb{N}$ be given. In order to construct a tiling using $k$ long dominos, one need to use $n-(p+1)k$ short dominos, so it amounts to select the position of the $k$ long dominos among the total of $n-pk$ dominos. In other words, there are $\binom{n-pk}{k}$ possible tilings of the $1\times n$ rectangle that use $k$ long dominos. Summing over all $k\geq 0$ gives the identity.

We therefore have in particular that $$ \forall a \in \mathbb{N},\ u_{pa} = \sum_{k\geq 0} \binom{p(a-k)}{k} $$

We will now use the following arithmetic lemma: $$ \begin{align*} \binom{pn}{k} &= 0\ mod(p) \quad \text{if $p$ does not divide $k$}\\ \binom{pn}{pk} &= \binom{n}{k}\ mod(p) \end{align*} $$ It is an immediate consequence of Lucas's theorem, but we can also rederive it by considering the following polynomial in $\mathbb{F}_p$: $$ \begin{align*} \sum_{k=0}^{pn} \binom{pn}{k} X^k &= (1+X)^{pn} \ mod(p) \\ &= ((1+X)^p)^n \ mod(p)\\ &= (1+X^p)^n \ mod(p)\\ &= \sum_{k=0}^n \binom{n}{k} X^{pk}\ mod(p) \end{align*} $$ identifying the coefficient of each monomial gives the identity. Thus it follows that $$ \begin{align*} u_{pa} &= \sum_{k\geq 0} \binom{p(a-k)}{k} \\ &= \sum_{k\geq 0} \binom{p(a-pk)}{pk} \ mod(p) \\ &= \sum_{k\geq 0} \binom{a-pk}{k} \ mod(p) \\ &= u_a \ mod(p) \end{align*} $$ Which gives a first proof of the result.

• Second proof (based on combinatorics/group actions): Let us note by $v_n$ the number of possible tilings of the $1\times n$ rectangle where we are eventually allowing the first long domino to be cut in order to fill the beginning and the end of the rectangle (in a sense, we are considering tilings of the $1 \times n$ cylinder). By considering the way to place the first domino, we clearly have $$ \left\{ \begin{array}{ll} v_n = 1, & 0\leq n \leq p\\ v_{n+p+1} = u_{n+p} + (p+1)u_n& \end{array}\right. $$ In other words, $(v_n)$ and $(u_n)$ satisfy the same recurrence relation in $\mathbb{F}_p$ so they must be equal modulo $p$. However, note that we can build a simple $\mathbb{F}_p$-action on the set of tilings of the $1 \times pa$ cylinder for $a\in \mathbb{N}$: cut the rectangle into $p$ rectangular blocks of size $1 \times a$ and permute the block cyclically (it is clear that it gives valid tiling if you see this as a rotation of the cylinder by $a$ units). Now the orbits of every tiling (ie. the tilings obtained when applying multiple times this cyclic permutation to a tiling) must be of size $p$ or $1$ because $p$ is prime. The orbits of size $1$ corresponds to the tilings that are fixed by the rotation, therefore they are composed of $p$ times the same block, corresponding to a tiling of a $1\times a$ cylinder. Therefore there are $v_a$ orbits of size $1$. Finally, we can conclude by regrouping tilings by orbits that $$ u_{pa} = v_{pa} = v_a = u_a \ mod(p) $$ which again concludes the proof.