In a length-n maintenance schedule where no two maintenance slots may be adjacent, why does the count satisfy f(n)=f(n-1)+f(n-2)?
answer
- where the adjacency constraint bites
- split the set, then add
- case on the final slot's state
- maintenance forces an idle predecessor
- empty schedule counts as one
basics
~10 sSplit on the last slot. Idle leaves any valid (n-1)-schedule; maintenance forces the previous slot idle, leaving any valid (n-2)-schedule. The two cases are disjoint and exhaustive, so their counts add.
solid answer
~40 sCondition on the last slot, because that is where the adjacency rule bites. If slot `n` is idle it constrains nothing, so the first `n-1` slots can be any valid schedule: `f(n-1)` of them. If slot `n` is maintenance, slot `n-1` is forced idle and the first `n-2` slots are free: `f(n-2)` of them. Every valid schedule falls in exactly one case, so `f(n) = f(n-1) + f(n-2)` for `n >= 2`. The base cases then decide everything downstream: `f(0) = 1`, because the empty schedule is one arrangement rather than none, and `f(1) = 2`. That yields 1, 2, 3, 5, 8, 13. Starting from `f(0) = 0` shifts the entire sequence and makes every later count wrong, which is the usual error here.
code
pseudocode · 8 linesf[0] = 1 // the empty schedule: one arrangement
f[1] = 2 // idle, or maintenance
for n from 2 to N:
f[n] = f[n-1] // last slot idle: rest is any valid schedule
+ f[n-2] // last slot maintenance: predecessor forced idle
return f[N]go deeper
Recall that a 'no two adjacent' count is built by a case split, not looked up. Being able to list every valid three-slot schedule by hand and land on five is the expected floor.
Explain the split on the final slot, why the two cases neither overlap nor miss anything, and why a two-step lookback needs exactly two initial conditions rather than one.
Show that you verify before you trust: brute-force the first few values, say aloud what a size-zero count means, and name the rule change that would deepen the lookback.
Read the count as a sizing result. An exponentially growing configuration space tells a design review that exhaustive validation of all schedules is off the table before anyone writes code.
## The object being counted A maintenance window is cut into **n** equal slots. Each slot is either **idle** or **under maintenance**, and the operating rule is that no two maintenance slots may sit next to each other — whatever is taken down must be back before the next thing is touched. Write **f(n)** for the number of distinct length-n schedules obeying that rule. Without the rule there would be `2^n` schedules, one per independent binary choice; the rule kills most of them, and the question is how many survive. The answer is not found by a formula lookup. It is found by turning the constraint into a **recurrence**: an equation that expresses the count for size `n` in terms of counts for smaller sizes, plus enough starting values to anchor it. ## Conditioning on the last slot The whole derivation is one case split, taken at the place the constraint actually acts — the boundary between the final slot and its predecessor. - If slot `n` is **idle**, it forbids nothing to its left. Slots `1..n-1` only have to be valid on their own, so this case contributes exactly `f(n-1)` schedules. - If slot `n` is **maintenance**, slot `n-1` is **forced** idle. Slots `1..n-2` are then unconstrained by the end of the schedule, so this case contributes `f(n-2)`. - The two cases are **disjoint** — a slot cannot be both states — and **exhaustive** — there is no third state. So the counts add rather than needing any correction term. That is `f(n) = f(n-1) + f(n-2)` for every `n >= 2`. Nothing in the argument is specific to maintenance: the same split counts any binary sequence with one forbidden adjacent pair. ## The base cases are not decoration A recurrence that looks back two steps needs exactly **two** starting values, and choosing them carelessly poisons everything after. | n | the valid schedules (I = idle, M = maintenance) | f(n) | |---|---|---| | 0 | the empty schedule | 1 | | 1 | I, M | 2 | | 2 | II, IM, MI | 3 | | 3 | III, IIM, IMI, MII, MIM | 5 | | 4 | — | 8 | `f(0) = 1` is the one people argue with. There is exactly **one** way to arrange nothing — the empty arrangement — and the recurrence needs that value to produce `f(2) = 3`, which brute force confirms (the only excluded length-2 schedule is MM, so 4 - 1 = 3). Setting `f(0) = 0` gives `f(2) = 2`, and every later value is off by one position in the sequence. ## The same recurrence, a different sequence Several classic counts obey `f(n) = f(n-1) + f(n-2)` and are **not** the same sequence: - **Tilings of a 2-by-n strip by dominoes**: condition on the right edge — one vertical tile leaves a 2-by-(n-1) strip, two stacked horizontal tiles leave 2-by-(n-2). Here `t(0) = 1` and `t(1) = 1`, giving 1, 1, 2, 3, 5, 8. - **Paths up n stairs taking steps of one or two**: the same split on the final step. The recurrence is the **rule of motion**; the initial conditions fix **where the sequence starts**. Here the schedule count and the tiling count differ by exactly one position: `f(n) = t(n+1)`. An answer that says "it is Fibonacci" without naming the starting values has not finished the job. ## The vocabulary, so the next step is available This recurrence is **linear** (each earlier term appears to the first power), **homogeneous** (no extra term independent of `f`), of **order 2** (it looks back two positions), with **constant coefficients** (both 1). Those four properties are exactly what a closed form by characteristic roots requires, which is why interviewers ask for the derivation before the formula. Change the rule and the shape changes with it: banning three maintenance slots in a row but allowing two gives a third-order recurrence, `f(n) = f(n-1) + f(n-2) + f(n-3)` with `f(0) = 1`, `f(1) = 2`, `f(2) = 4`. Adding a cap on the total number of maintenance slots needs a second index and leaves this family altogether. ## What is actually being checked - You say **what n is** before writing anything — slots, not maintenance events. - You state the split and justify that it is disjoint and exhaustive, rather than asserting the recurrence. - You supply **as many base cases as the lookback depth**, and you can defend `f(0) = 1`. - You sanity-check by brute force at `n = 2` and `n = 3` instead of trusting the algebra.
- Domino tilings of a 2-by-n strip obey the same recurrence — why is the count not the same sequence?Because the initial conditions differ. The tiling count starts at `t(0) = 1`, `t(1) = 1` and runs 1, 1, 2, 3, 5, 8, while the schedule count starts at 1, 2 and runs 1, 2, 3, 5, 8. The recurrence fixes the step rule; the starting values fix the position. Here `f(n) = t(n+1)`.
- What changes if three maintenance slots in a row are banned but two in a row are allowed?The lookback deepens to three. Condition on the length of the trailing maintenance run — zero, one or two — giving `f(n) = f(n-1) + f(n-2) + f(n-3)` with three base cases `f(0) = 1`, `f(1) = 2`, `f(2) = 4`. Check it: `f(3) = 7`, which is the 8 length-3 schedules minus MMM.
- How would you convince yourself the recurrence is right before relying on it?Enumerate the small cases by hand and compare. Listing every valid schedule for three slots gives five, and the recurrence gives `f(3) = f(2) + f(1) = 3 + 2 = 5`. Two agreeing values past the base cases catch nearly every off-by-one in the split or the starting values.
saying these in an interview costs you the question
- Sets f(0) = 0, shifting every later count by one position
- States the recurrence but supplies only one initial condition
- Answers 2^n minus the number of adjacent maintenance pairs
- Assumes any f(n)=f(n-1)+f(n-2) is the same sequence whatever the start
- Says the count doubles per slot because each slot has two states