Help solve recurrence : f(x) = 2f(x-1) + x While trying to analyze the time complexity of the heapify algorithm ,
I came up with the following recurrence for it's time complexity in terms of heap height:
T(h) = 2T(h-1) + h 

Could you help me approach this recurrence?

$$a_k = 2a_{k-1} + k$$
$$\implies \dfrac{a_k}{2^k} = \dfrac{a_{k-1}}{2^{k-1}} + \dfrac{k}{2^k}$$
$$\implies \dfrac{a_k}{2^k} - \dfrac{a_{k-1}}{2^{k-1}} = \dfrac{k}{2^k}$$
$$\implies \sum_{k=1}^{n} \left(\dfrac{a_k}{2^k} - \dfrac{a_{k-1}}{2^{k-1}}\right) = \sum_{k=1}^{n} \dfrac{k}{2^k}$$ 
$$ \implies \dfrac{a_n}{2^n} - \dfrac{a_0}{2^0} = \sum_{k=1}^{n} \dfrac{k}{2^k} $$ 
Note that the R.H.S. is an Arithmetic-Geometric Progression. Thus,  
$$\sum_{k=1}^{n} \dfrac{k}{2^k} = \dfrac{1}{2^n}(2^{n+1} - n -2)$$
$$\implies \dfrac{a_n}{2^n} - \dfrac{a_0}{2^0}= \dfrac{1}{2^n}(2^{n+1} - n -2) $$ 
$$ \displaystyle \implies \boxed{a_n = 2^n(a_0 + 2) - n -2} $$
