В каком месте доказательства допущена ошибка?

Где именно в приведённом доказательстве была допущена ошибка? 

Переформулируйте следующий вопрос для улучшения ясности и структуры, при этом сохраняя исходный смысл:

На основании предоставленного кода и описания задачи, покажите, что сортировка поручений по времени, необходимому для их выполнения подчинёнными, приведёт к оптимальному решению. Начните с первого шага математической индукции, рассмотрев случай, когда n равно 1, что соответствует наличию только одной задачи.

Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи. 
 
 Правильное доказательство весьма простое и без индукции. Общее время будет 
Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))
 . 
 Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится.  Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное. 
 Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.