Difference between revisions of "2.37"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "On careful observation , one can see that the sum of any row is just <math>3^{n-1}</math> this is the sum for the series . This can even be computed using a series as shown b...")
(No difference)

Revision as of 19:55, 10 September 2020

On careful observation , one can see that the sum of any row is just [math]\displaystyle{ 3^{n-1} }[/math] this is the sum for the series . This can even be computed using a series as shown below

1=a0
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 next row; once directly below it, and also in left and right element below it.

So sum of elements in [math]\displaystyle{ (n+1) }[/math]th row will be 3*(sum of elements in [math]\displaystyle{ n }[/math]th row).

Hence, S(n) = [math]\displaystyle{ 3^{n-1} }[/math] (Base case : For 1st row, sum is 1)

Back to Chapter 2