Harvard-MIT Mathematics Tournament

Solution:
First, we prove the statement in the hint: adding the $i$th term of the sum for $S(n-1, r-1)$ to the $i$th term for $S(n-1, r)$, for each $i$, we get that $S(n-1, r-1)+S(n-1, r)$ equals
$$\begin{gathered} \left(\binom{n-2}{r-2}+\binom{n-2}{r-1}\right)+\left(\binom{n-2}{r-1}+\binom{n-2}{r}\right)+\cdots \\ \cdots+\left(\binom{n-2}{n-3}+\binom{n-2}{n-2}\right)+\binom{n-2}{n-2} \\ =\binom{n-1}{r-1}+\binom{n-1}{r}+\cdots+\binom{n-1}{n-1}=S(n, r) . \end{gathered}$$
Now we can prove the main statement by induction on $n$. The base case $n=1$ is clear. If the statement holds for $n-1$, then first suppose $r>1$. Then the number in row $n$, $r$ columns to the left, is the sum of two of the three numbers above it, which, by the induction hypothesis, are at most $S(n-1, r-1), S(n-1, r), S(n-1, r+1)$ respectively. Since the first two of these are greater than the last (because the summation formula gives $S(n-1, r-1)=S(n-1, r)+\binom{n-1}{r-2}$ and $S(n-1, r)=S(n-1, r+1)+\binom{n-1}{r-1}$), we have an upper bound of $S(n-1, r-1)+S(n-1, r)=S(n, r)$ by the above. So the result follows by induction. Finally, in the case $r=1$, the quantity in question is just $2^{n-1}$, and the result holds by Problem 1.