Finite sequence with no two consecutive terms $\newcommand{\N}{\mathbb{N}}$
Let $n \in \N$, we define $[n] \doteq \{1 , \ldots, n \}$. Consider the following $$ H_n^k \doteq \{ z \in [n]^k  \mid  \forall i \in [k-1]: \ z_{i+1} \neq z_i + 1 \} $$
Where, $z_i$ is the value at the position $i$. In other words, we are considering the sequences of length $k$ with elements in $[n]$, such that for every position the next one is not the succesor. For example the sequence $z = 13476 \notin H_7^5$.
How to calculate $\left | H_{n}^k \right |$ ?
Let me show you my attempt. Let's define $$ F_{n}^{i} = \{ z \in [n]^k \mid z_{i+1} = z_i + 1 \} $$ then, what we are looking for is $$n^k - \left | \bigcup\limits_{i=1}^{k-1} F_n^i    \right |  $$Afterwards, what I wanted to use is the inclusion-exclusion principle but I got in troubles when I try to calculate the cardinal of the intersection of any of them.
Any suggests?
Regards!
 A: The numbers $|H_n^k|$ can be obtained via the linear recurrence relation
$$ |H_n^k| = \sum_{i=1}^{n} (-1)^{i+1}(n-i+1)|H_n^{k-i}|, $$
using the convention that $H_n^k$ is empty if $k<0$, and $|H_n^0|=1$.
To prove this formula, we break $H_n^k$ into the following subsets:
$$J_n^k(i) := \{ z\in H^k_n \ | \ z_1 = i \}  \quad (i=1,\ldots, n).$$
In other words, $J_n^k(i)$ is the set of sequences in $H_n^k$ starting with $i$. Obviously, $|H_n^k| = \sum_{i=1}^n |J_n^k(i)|$.  Moreover, we have the following:


*

*$|J_n^k(n)| = |H_n^{k-1}|$.  Indeed, if a sequence starts with $n$, then the remaining $k-1$ terms can be any sequence in $H_n^{k-1}$.

*For $j=1,\ldots,n-1$, we have $|J_n^k(j)| = \sum_{i=1}^{n+1-j}(-1)^{i+1}|H_n^{k-i}|$.  To see this, notice that if a sequence starts with $j$, then the remaining $k-1$ terms can be any sequence in $H_n^{k-1}$ that does not start with $j+1$.  Thus $|J_n^k(j)| = |H_n^{k-1}|-|J_n^{k-1}(j+1)|$.  The above equality is then obtained by induction.


Therefore we have $|H_n^k| = \sum_{j=1}^n |J_n^k(j)| = \sum_{j=1}^n \sum_{i=1}^{n+1-j}(-1)^{i+1}|H_n^{k-i}| = \sum_{i=1}^{n} (-1)^{i+1}(n-i+1)|H_n^{k-i}|$.
This proves the recurrence relation.
Using this, it is easy to compute the first terms of a sequence of $|H_n^k|$.  For instance, for $n=3$ and starting with $k=0$, we get $1,3,7,16,37,86,200,465,1081, \ldots$ (which, incidentally, is sequence A095263 of the OEIS).
General methods to solve linear recurrence relations could also be applied from there.
