Recall that the total time to execute the dynamic programming algorithm to compute an Optimal Static Binary Search tree shape is given by the expression:

Total Time = Time to fill in all diagonals

= sum(k = 1 to n) ( (number of entries in kth diagonal) *

(time to compute the value of one cell in the kth diagonal) )

= sum(k = 1 to n) ( (n + 1 - k) * k )

Show that the expression above simplifies O(n3). Show all of your work. Show each step in your derivation. You may use the identity that

sum(k = 1 to n) ( k2 ) = ( n (n+1) (2n+1) ) / 6