HMMT 2004 T3

Let

$$S(n, r)=\binom{n-1}{r-1}+\binom{n-1}{r}+\binom{n-1}{r+1}+\cdots+\binom{n-1}{n-1}$$

for all $n, r>0$, and in particular $S(n, r)=0$ if $r>n>0$. Prove that the number in row $n$ of the table, $r$ columns to the left of the 1 in the top row, is at most $S(n, r)$. (Hint: First prove that $S(n-1, r-1)+S(n-1, r)=S(n, r)$.)