How to derive the worst case time complexity of Heapify algorithm?

Question

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure.

I am asking this question in the light of the book "Fundamentals of Computer Algorithms" by Ellis Horowits. I am adding some screenshots of the algorithm as well as the derivation given in the book.

Algorithm:

Derivation for worst case complexity:

I understood the first part and last part of this calculation but I cannot figure out how 2^(i-1) x (k-i) changed into i2^(k-i-1).

All the derivations I can find in the internet takes a different approach by considering the height of the tree differently. I know that approach also leads to the same answer but I would like to know about this approach.

You might need the following information:

2^k-1 = n or approximately 2^k = n, where k is the number of levels, starting from the root node and the level of root is 1 (not 0) and n is the number of nodes.

Also the worst case time complexity of the Adjust() function is proportional to the height of the sub-tree it is called, that is O(log n, where n is the total number of elements in the sub-tree.

Answer 1

It's a variable substitution.

First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when i = k, k-i = 0). So, the range of the first summation can be written as 1 <= i <= k-1. Now, substitute i with k-i. i iterates over the set {1, 2, ... , k-1} and k-i iterates over the set {k-1, ... 2, 1}, they are the same set, therefore, we can do this substitution.