Problem
ALG-B1-M05-P023 Sequences with a Required Hit
How many positive integer sequences \(a_1,\ldots,a_n\) contain at least one term equal to \(4\) or \(5\), and any two neighbouring terms differ by at most \(2\)?
First count sequences with minimum term at most \(5\), then subtract the extra ones.
Fix the differences \(b_i=a_{i+1}-a_i\). Each difference can be \(-2,-1,0,1,2\), giving \(5^{n-1}\) choices.
For each difference sequence, exactly one original sequence has minimum \(1,2,3,4,5\). Thus there are \(5^n\) sequences with minimum at most \(5\).
The extra ones are those with no \(4\) or \(5\). If such a sequence has minimum at most \(5\), step size at most \(2\), and contains a value greater than \(5\) and a value less than \(4\), it must pass through \(4\) or \(5\). Hence the extra sequences consist only of \(1,2,3\). There are \(3^n\) of them. Answer: \(5^n-3^n\).
Preserves the difference-sequence architecture and subtracting extra cases.