Problem
ALG-B1-M05-P013 How Many Sequences
#13
★★★★☆ Level 4 of 5
How many positive integer sequences \(a_1,\ldots,a_n\) have minimum term at most \(4\) and \(|a_{i+1}-a_i|\le1\)?
Fix the differences and the minimum term.
The difference sequence has \(n-1\) terms, each equal to \(-1,0,1\), giving \(3^{n-1}\) choices.
For each difference sequence, all original sequences are obtained by adding the same constant to all terms. Exactly one has minimum \(1,2,3,4\). Therefore the answer is \(4\cdot3^{n-1}\).
This prepares for a harder problem with forbidden values.