Thanks to Taussig's hint for using the Inclusion-Exclusion Principle. I have tried it by myself. I am posting this approach as another answer for future reference.
Let $a_{i,j}$ denote the number of $i$-element subsets of $\{1,2,...,j\}$, where each of such subsets does not contain three consecutive integers.
Let $E_{m,n}$ denote the event to involve $n$ consecutive integers starting from $m$. For example, $E_{1,3}$ represents the event to have integers $1,2,3$.
Let $N(E_{m,n})$ denote the number of such subsets that satisfy $E_{m,n}$.
Note. $E_{m,n}$ changes meaning when the corresponding $a_{i,j}$ changes.
Okay. Now let us do the counting!
- $a_{4,10}$
$=\binom {10}{4}-(N(E_{1,3})+N(E_{2,3})\cdot\cdot\cdot+N(E_{8,3}))+(N(E_{1,3}\cap E_{2,3})+N(E_{2,3}\cap E_{3,3})+\cdot\cdot\cdot+N(E_{7,3}\cap E_{8,3}))$
$=210-7\times8+1\times7$
$=161$
- $a_{5,10}$
$=\binom {10}{5}-(N(E_{1,3})+N(E_{2,3})\cdot\cdot\cdot+N(E_{8,3}))+(N(E_{1,3}\cap E_{2,3})+N(E_{2,3}\cap E_{3,3})+\cdot\cdot\cdot+N(E_{7,3}\cap E_{8,3}))+(N(E_{1,3}\cap E_{3,3})+N(E_{2,3}\cap E_{4,3})+\cdot\cdot\cdot+N(E_{6,3}\cap E_{8,3}))-(N(E_{1,3}\cap E_{2,3}\cap E_{3,3})+N(E_{2,3}\cap E_{3,3}\cap E_{4,3})+\cdot\cdot\cdot+N(E_{6,3}\cap E_{7,3}\cap E_{8,3}))$
$=252-\binom {7}{2}\times8+7\times6+6-6$
$=126$
- $a_{6,10}=45$. I am leaving the details to you so that you could possibly have some fun!
Although Inclusion-Exclusion generalizes well, it is not always the best approach to such a problem. In this problem, both Inclusion-Exclusion and the Direct approach result in messy Math. From my limited knowledge, that leaves recursion.
Let $f(n)$ denote the number of satisfying words (no instance of $k$ consecutive letters), as a function of $(n)$. Index the letters, from left to right as $L_1, L_2, \cdots, L_n.$ This means that the rightmost letter is $L_n$ and the leftmost letter is $L_1$.
For $r \in \{1,2,\cdots,k-1\},$ let $f(n,r)$ denote the number of satisfying words that end with $r$ consecutive letters. That is:
Let $f(n,1)$ denote the number of satisfying words,
where $L_{n-1} \neq L_n$.
Let $f(n,2)$ denote the number of satisfying words,
where $L_{n-1} = L_n$ and $L_{n-2} \neq L_{n-1}.$
Let $f(n,3)$ denote the number of satisfying words,
where $L_{n-2} = L_{n-1} = L_n$ and $L_{n-3} \neq L_{n-2}.$
Let $f(n,4)$ denote the number of satisfying words,
where $L_{n-3} = L_{n-2} = L_{n-1} = L_n$ and $L_{n-4} \neq L_{n-3}.$
$\cdots$
Let $f(n,k-1)$ denote the number of satisfying words, where
$L_{n-(k-2)} = L_{n-(k - 3)} = \cdots = L_{n-2} = L_{n-1} = L_n$ and $L_{n-(k-1)} \neq L_{n-(k-2)}.$
It is to be understood that for $n,r,k \in \Bbb{Z^+},$ such that $n < r \leq k-1,$ that $f(n,r) = 0.$ That is, when $n$ is less than $k-1$, you can't have a word with $n$ letters, that ends with more that $n$ consecutive letters.
Then, you have the following formulas that illustrate how $f(n)$ may be recursively computed:
$\displaystyle f(n) = \sum_{r=1}^{k-1} f(n,r).$
$f(n+1,1) = f(n) \times 25.$
That is, you have $25$ choices for constructing a satisfying word with $n+1$ characters by appending a character to the end of any satisfying word with $n$ characters, such that $L_n \neq L_{n+1}.$
For $2 \leq r \leq k-1$,
$f(n+1,r) = f(n,r-1)$.
That is, there is only one way of converting a $n$ character sequence that ends with $(r-1)$ consecutive letters into a $(n+1)$ character sequence that ends with $(r)$ consecutive letters.
The following table, with $k = 4$ illustrates how $f(n)$ may be recursively computed for $n \in \{1,2,3,4,5\}.$
\begin{array}{| r | r | r | r | r |}
\hline
n & f(n,1) & f(n,2) & f(n,3) & f(n) \\
\hline
1 & 26 & 0 & 0 & 26 \\
\hline
2 & 26 \times 25 & 26 & 0 & (26)^2 \\
\hline
3 & (26)^2 \times 25 & 26 \times 25 & 26 & (26)^3 \\
\hline
4 & (26)^3 \times 25 & (26)^2 \times 25 & 26 \times 25 & \displaystyle 25 \times \left[\sum_{a=1}^3 (26)^a\right] \\
\hline
5 & \displaystyle (25)^2 \times \left[\sum_{a=1}^3 (26)^a\right] & (26)^3 \times 25 & (26)^2 \times 25 & \displaystyle (25)^2 \times \left[\sum_{a=1}^3 (26)^a\right]\\
& & & & + \left[(26)^3 \times 25\right] \\
& & & & + \left[(26)^2 \times 25\right]\\
\hline
\end{array}
Best Answer
Hint: If $T_n$ is the amount of such sequences of length $n$, $$T_n=3\left(T_{n-1}+T_{n-2}\right),$$ for $n\geq3$.