Counting words of length n from k-sized alphabet with no substring of k consecutive distinct letters
How many words of length n are there, if we have an alphabet of k distinct letters, but the words cannot contain any substring that is made of k consecutive distinct letters, i.e, no k-length substring that consists of the entire alphabet?
Other than that, no restrictions apply: any amount of distinct letters may be used throughout the entire word, and any letter can be used as many times as we like, as long as every substring inside the length n word complies with the rules above.
There is the obvious case of which results in 2 words, for every n, because you can only start with either letter, and they alternate.
For the larger case, I have come up with a recursive formula:
With d being the current length of consecutive distinct letters, and i the current word length.
At every step, we can either use a letter other than the previous d letters, in which case the length is increased by one, and the chain-length d of distinct consecutive letters is also increased by one. In this case, there are such letters we can use at the stage, each subsequently resulting in the same contribution.
Or, we can use a letter already in the last d letters. In this case, the position of the letter matters. If we use the last of the d letters, a whole new chain begins. If instead we use the second last d letter, then a chain of length 2 of consecutive distinct letters begins. The 3rd last would result in a chain of length 3 and so on.
I was wondering if there is a another way to count the amount of such words, perhaps using matrices or combinatorics?