I'm trying to figure out how many of the strings from an alphabet of characters, say , do NOT contain a particular substring which itself contains no overlapping substrings. I figure that a decent recurrence relation is where is the number of length strings with no substring and:

This is function-able but it would be great to have this as a closed form equation. Thanks in advance for any ideas.

Addie