a) Find a recurrence relation for $a_n$, the number of sequences of $2$'s, $3$'s, and $4$'s summing to $n$ with the subsequence $324$ not allowed.
b) Repeat part a) but now with the requirement that you cannot have the subsequence $44$.
Okay, So I do know how to solve this problem. The issue is its process.
For the first problem, the answer is:
$$a_n = a_{n-2} + a_{n-3} + a_{n-4} - a_{n-9}$$
because subsequence 324 should be removed from the possibilities. The second answer is:
$$a_n = a_{n-2} + a_{n-3} + (a_{n-6}+a_{n-7})$$
because after 4 there should be either $2$ or $3$, not $4$.
I don't fully comprehend the logic here. First of all, in the process of removing subsequences including $324$, is $-a_{n-9}$ a fair move? If I remove $3+2+4 = 9$ through $-a_{n-9}$, shouldn't that include other combinations that are not within the constraints, such as $432$ and $333$?
Second of all, according to the first logic, shouldn't we apply $-a_{n-8}$ instead of $+(a_{n-6}+a_{n-7})$ in the second section?
I am not sure if I'm being clear enough to see my point here, but I'd really appreciate some insights. It's kinda confusing. What am I missing here?
Thank you in advance.
This solution is a bit tricky. The initial idea is that every sequence looks like one of these three: $$ \begin{array}{c} \dots(\text{valid sequence summing to }n-2)\dots2\\ \dots(\text{valid sequence summing to }n-3)\dots3\\ \dots(\text{valid sequence summing to }n-4)\dots4 \end{array} $$ and the number of ways to choose the "valid sequence summing to $n-i$" part is $a_{n-i}$. This addition is valid because the above three sets are disjoint. However, just because a sequence $s$ is valid, this does not mean that sequence $s+4$ attained by appending a $4$ to the end of $s$ is valid. When $s$ ends with $32$, you end up with $324$ at the end. It turns out these are the only exceptional cases; these bad cases look like $$ \dots(\text{valid sequence summing to }n-9)\dots324 $$ and are therefore exactly subtracted out by $a_9$. This only counts the sequences above, and not those ending with $234$ or $333$; $a_{n-9}$ only specifies how to choose what comes before, not the sequence of three at the end, so (...valid sequence...)$324$ is the only case which is subtracted out.
Again, every valid sequence looks like one of these three: $$ \begin{array}{c} \dots(\text{valid sequence summing to }n-2)\dots2\\ \dots(\text{valid sequence summing to }n-3)\dots3\\ \color{red}{\dots(\text{valid sequence summing to }n-4)\dots4} \end{array} $$ However, not every string in the last case is valid: we must only count the cases where "valid sequence summing to $n-4$" does not end with a $4$. These look like either $$ \dots(\text{valid sequence summing to }n-6)\dots24\\ \dots(\text{valid sequence summing to }n-7)\dots34\\ $$ so replacing the $\color{red}{red}$ category with the two above gives a valid recurrence.
It's worth nothing that there is a different solution to (2) which is more similar to the solution to (1). Namely, you could throw out the bad cases where the string ends with $44$, for the recurrence $$ a_n=a_{n-2}+a_{n-3}+a_{n-4}-a_{n-8} $$ In other words, for your second question, you are correct. It just happens to be that there is more than one correct way to approach this problem.Correction: Actually, the same method does not work for a subtle reason (at least, it was hard for me to see!). The problem is that the forbidden sequence $44$ can overlap with itself, so the same subtraction trick does not work so cleanly. For example, when you subtract out $a_{n-8}$, the subtracted sequences include those that look like $\_\dots\_444$, but these were not included in the first place. Really, you would need to add these back in, but this would result in unwanted things being added back in, and so on, resulting in a recurrence which does not have a bounded number of terms.