Recurrence relation in a Student Attendance problem

Question

I'm having trouble understanding the solution to a coding contest problem.

Student Attendance Problem

Suppose a student's attendance is recorded as a string, e.g.

PPAPPPPLPPPLPPLLAPPPP

where the letters represent Present, Late, and Absent. A reward is given to the student who satisfies the following criteria,

1. No more than one absence.
2. No triple consecutive lateness, e.g. LLL.

Given an attendance record of length $n$, then, how many rewardable records exist?

For example, for $n=2$, only AA fails to be rewarded, of $3^2$ possible strings, so the answer is $8$.

Official Solution

The official solution attempts to build a recurrence relation, starting with this diagram:

It explains: Let $f[n]$ represent the number of rewardable cases for a string of length $n$. Let's divide into two cases,

1. Strings ending with L.
2. Strings ending with P. (I don't know why it says N in the diagram; typo, I think.)

It's easy to see that the second case is rewardable as long as the piece preceding the P, $f[n-1]$, is rewardable.

However, the L case must be split into four pieces, as shown. There, the author claims that the only troublesome piece is the last, ending the string in LLL. His exact words are,

Out of the four combinations possible at the end, the fourth combination, ending with a $LL$ at the end leads to an unrewardable string. But, since we've considered only rewardable strings of length $n-3$, for the last string to be rewardable at length $n-3$ and unawardable at length $n-1$, it must be preceded by a $PP$ before the $LL$.

Thus, accounting for the first string [left branch] again, all the rewardable strings of length $n-1$, except the strings of length $n−4$ followed by $PLL$, can contribute to a rewardable string of length $n$. Thus, this string accounts for a factor of $f[n-1] - f[n-4]$ to $f[n]$.

Thus, the recurring relation becomes:

$$f[n] = 2f[n-1] - f[n-4]$$

I was hoping someone could put this explanation in their own words, because I don't understand this author's. And he has made several typos in his explanation already, so I'm not sure I trust this explanation.

Another thing I don't understand is why the first of the four cases isn't also problematic, since if the $n-5$th and $n-4$th characters were L, then we'd also have an unrewardable string.

Any hints as to untangling the author's explanation would be appreciated. Thank you.

P.S. The author is intentionally ignoring A at this stage, to be considered separately.

Answer 1

It really is a lot easier than the author makes out.

You have $3$ possible mutually exclusive and exhaustive endings to valid sequences of length $n$

$$(\text{valid sequence length $n-1$})\, \text{P}$$ $$(\text{valid sequence length $n-2$})\, \text{PL}$$ $$(\text{valid sequence length $n-3$})\, \text{PLL}$$

or, in other words

$$f[n]=f[n-1]+f[n-2]+f[n-3]\tag{Answer 1}$$

with $f[0]=1,\, f[1]=2,\, f[2]=2^2=4$.

But since

$$f[n-1]=f[n-2]+f[n-3]+f[n-4]$$

we have

$$f[n]=2f[n-1]-f[n-4]\tag{Answer 2}$$

with the extra initial value $f[3]=2^2+2+1=7$.

---

The overall answer (including the possibility of an absence) will be

$$f[n]+\sum_{k=1}^{n}f[k-1]f[n-k]$$

because there are $f[n]$ valid sequences with no absence and $\sum_{k=1}^{n}f[k-1]f[n-k]$ sequences with $1$ absence (the absence A can be in positions $k=1\ldots n$ with a valid sequence of Ps and Ls either side of the A).