jmc

Question

Consider the triangular array of numbers with 0, 1, 2, 3, along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows 1 through 6 are shown. arrayccccccccccc & & & & & 0 & & & & & & & & & 1 & & 1 & & & & & & & 2 & & 2 & & 2 & & & & & 3 & & 4 & & 4 & & 3 & & & 4 & & 7 & & 8 & & 7 & & 4 & 5 & & 11 & & 15 & & 15 & & 11 & & 5 array Find the sum of the numbers in the 100th row. Your answer should use exponential notation, in simplest form.

Accepted Answer

Let f(n) denote the sum of the numbers in the nth row. We start by looking at an example. Suppose we take the 5th row, make a copy of every number, and send each copy to the fifth row. FIGURE Currently, the sum of the numbers in the fifth row is exactly double the sum of the numbers in the fourth row, because it contains two copies of every number in the fourth row. To make it look like the fifth row in the actual triangle, all we must do is add 1 to the first and last numbers in the row. Thus, f(5) = 2f(4) + 2. More generally, f(n) = 2f(n - 1) + 2for any n 2. Let g(n) = f(n) + 2. Then f(n) = g(n) - 2, so g(n) - 2 = 2(g(n - 1) - 2) + 2.This simplifies to g(n) = 2g(n - 1). Since g(1) = 2, it follows that g(n) = 2^n. Then f(n) = 2^n - 2. In particular, f(100) = 2^100 - 2.