Both sequences a and b are concave.

Show that if both a and b are concave, then the sequence z_i=a_i+b_k-i is also concave as a function of i. Also, give a divide-and-conquer algorithm to compute c_k running in time O(logk). Give a brief (2-3) and informal argument for correctness

You want to buy a new laptop and a new phone but you don't know how much to spend on each item. You have done your research and have quantified how happy you will be spending your money on each of the items. You know that if you spend i dollars on a laptop and j dollars on a phone, your total happiness is ai + bj, for two non-decreasing sequences ao, ai,..., an and bo,bi,... ,bn that you have calculated. Given that you have a budget of k dollars, how should you spend your money? Your goal is now to calculate the maximum achievable happiness for some budget Bedse salving the pbofns drgs as you spend more money on the item. We call such a sequence s, concave, which means that s - s,-si when lSi<.>