From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

On careful observation, one can see that the sum of any row is just this is the sum for the series. This can even be computed using a series as shown below

1 1 1 
a1 a0 a2

now a(mid) of the next line becomes the a(0) +a(1) +a(2) that it this mid element is always the sum of the middle three elements

Alternate explanation :

Every element in the current row will be used 3 times in the next row; once directly below it, and also in left and right element below it.

So sum of elements in th row will be 3*(sum of elements in th row).

Hence, S(n) = (Base case : For 1st row, sum is 1)

Back to Chapter 2