(note that we will consider the scenario where only sequence b is concave and a is not)

Defining i(k) as the highest index that maximizes the value a_i+b_ki, prove that i(k) is a non-decreasing function of k, i.e.i(k)i(k+ 1), when b is a concave sequence but a is not.

if you can, please do the following

You have a backpack that can hold up to k pounds and can be filled with pixie dust or dragon scales. The value of i pounds of pixic dust is determined by the non-decreasing sequence ai, while the value of j pounds of dragon scales is determined by the non-decreasing sequence bj. Given a weight limit k and sequences ao ... Com and bo ... Or, your goal is to calculate the maximum value you can obtain by filling the backpack with some combination of pixic dust and dragon scales. Note that in some cases the rate of increase in an item's value decreases the more you have of it. Such a sequence 8; is called concave and satisfies that s; si 1 is a decreasing function of i. Provide a divide and conquer algorithm to compute vk for k = 0,1, ... n that runs in time O(n log n) along with a brief (2-3 lines) proof of correctness. You may assume that n is a power of 2 for simplicity