Asymptotic Analysis of Heapify

A quick analysis of Heapify

    void Heapify(int [] a, int size){
        for (int parent = size/2; parent >= 0; parent--){
            fixMaxHeap(a,size,parent);
        }    
    }
    void fixMaxHeap(int [] a, int size, int parent){
        int leftChild = parent*2+1;
        int rightChild = leftChild+1;
        if (!(leftChild < size)) return; //no rightChild OK
        
        int bigChild;
        if (rightChild >= size)
            bigChild = leftChild; //only child
        else if (a[leftChild] < a[rightChild])
            bigChild = leftChild;//leftSibling is bigger
        else
            bigChild = rightChild;
        
        if (a[bigChild] > a[parent]){
            swap(a,parent,bigChild);
            fixMaxHeap(a, size, bigChild);
        }
    }

will often lead one to the incorrect O(n lg n)
certainly the loop in Heapify is order N and the fixMapHeap code is O(lg N)
which would seem at first a strong argument that the code is O(n lg n)
but heapify requires deeper analysis. One can find:
let k = lg n

i=1;
Σ x·2^(k-x)
i<=k

or

i=1;
Σ (k-x)·2^x
i<=k

but this hardly reveals the solution. pushing one may expand the above formulas to
(1)2^(k-1)+(2)2^(k-2)+(3)2^(k-3)+...+(k-1)2^(k-(k-1))+(k)2^(k-k)

this can be cleverly rewritten as k sums:

(1)2^(k-1)+(1)2^(k-2)+(1)2^(k-3)+...+(1)2^(k-(k-1))+(1)2^(k-k)
          +(1)2^(k-2)+(1)2^(k-3)+...+(1)2^(k-(k-1))+(1)2^(k-k)
                      (1)2^(k-3)+...+(1)2^(k-(k-1))+(1)2^(k-k)
                                +...+(1)2^(k-(k-1))+(1)2^(k-k)
                                 ...+(1)2^(k-(k-1))+(1)2^(k-k)
                                                   +(1)2^(k-k)

the value of these terms follow the well known pattern
2^1+2^2+2^3+...+2^k = (2^(k+1))-1
where the sum of all previous terms is equal to twice the largest term-1;
going back to our series the first line
2^(k-1)+2^(k-2)+2^(k-3)+...+2^(k-(k-1))+(1)2^(k-k)
is now quickly seen to be (2^K)-1
and the next line will be found to be 1/2 as large meaning we have the familiar pattern
(2^K)+2^(k-1)+2^(k-2)+...+2^(k-k)
which gives us
2^(k+1)
remember at the beginning we said k = lg n? that gives us 2^(lg n +1)
since 2^lg n == n 2^(k+1)
we have 2n or 2^(k+1)
O(n)