Combinatorial approach to prove divisibility results with the sequence $u_{n+p+1} = u_{n+p} + u_{n}$ in $\mathbb{F}_p$ 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. 
 A: 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.

