Harvard-MIT Mathematics Tournament

Problem:

An infinite table of nonnegative integers is constructed as follows: in the top row, some number is $1$ and all other numbers are $0$'s; in each subsequent row, every number is the sum of some two of the three closest numbers in the preceding row. An example of such a table is shown below.

$$\begin{array}{ccccccccccc} \cdots & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ \cdots & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & \cdots \\ \cdots & 0 & 0 & 0 & 1 & 1 & 2 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 0 & 1 & 1 & 3 & 3 & 2 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 2 & 4 & 4 & 6 & 3 & 2 & 0 & \cdots \\ . \cdot & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$

The top row (with the one $1$) is called row $0$; the next row is row $1$; the next row is row $2$, and so forth.

Note that the following problems require you to prove the statements for every table that can be constructed by the process described above, not just for the example shown.

1. Show that any number in row $n$ (for $n>0$) is at most $2^{n-1}$.