= Solution
Regardless of which branch is taken, $r(n)\leq r(n-1)+n$. Starting from zero and applying <induction> gives
$$
\boxed{0\leq r(n)\leq\sum_{i=1}^{n}i=\frac{n(n+1)}2.}
$$
For the inductive step, add $n$ to the bound $(n-1)n/2$ for the previous value. The subtraction branch gives an even smaller result, and positivity is checked there. This bound need not describe the actual growth sharply; it is sufficient to size a finite membership representation for a requested prefix.
Back to article page
