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: To solve the recurrence $$a_h=2a_{h-1}+h \tag{1}$$ write $$b_h=a_h+h$$ Adding $h$ to both sides of $(1)$ gives $$b_h=2b_{h-1}+2$$  Can you take it from here?
A: $$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} $$
A: For another solution, suppose $f(x)=ax+b$. If $f(x)=2f(x-1)+x$, then
$$ax+b=2a(x-1)+2b+x=(2a+1)x+2b-2a$$
and so
$$(a+1)x=b+2a.$$
The above gives $0=b+2a$. For an initial value $f(0)=x_0$, $f(0)=b=x_0$. Thus $f(x)=x_0-\frac{x_0}{2}x$.
I guess the first line might be sort of unsatisfying, but it is pretty reasonable to guess that such an $f$ could be linear, and if that didn't work, some other polynomial. The problem of finding all such functions $f$ is a different question, though, so I think it suffices to find just one.
A: You can write it as a matrix equation:
$$\begin{pmatrix}1\\ T_h\end{pmatrix}=\begin{pmatrix}1&0\\ h&2\end{pmatrix}{1\choose T_{h-1}}=\begin{pmatrix}1&0\\ h&2\end{pmatrix}\begin{pmatrix}1&0\\ h-1&2\end{pmatrix}{1\choose T_{h-2}}=\\
\begin{pmatrix}1&0\\ (1+2)h-2&2^2\end{pmatrix}\begin{pmatrix}1&0\\ h-2&2\end{pmatrix}{1\choose T_{h-3}}=\\
\begin{pmatrix}1&0\\ (1+2+2^2)h-(2+2\cdot 2^2)&2^3\end{pmatrix}\begin{pmatrix}1&0\\ h-3&2\end{pmatrix}{1\choose T_{h-4}}=\cdots=\\
\begin{pmatrix}1&0\\ (1+2+\cdots+2^{h-1})h-(2+2\cdot 2^2+\cdots+(h-1)\cdot 2^{h-1}&2^h\end{pmatrix}{1\choose T_0}=\\
\begin{pmatrix}1&0\\ (2^h-1)h-(2^hh-2^{h+1}+2)&2^h\end{pmatrix}{1\choose T_0}=\\
\begin{pmatrix}1&0\\ 2^{h+1}-h-2&2^h\end{pmatrix}{1\choose T_0}=\\{1\choose 2^{h+1}-h-2+2^hT_0}.$$
A: $T(h)=2T(h-1)+h=2(2T(h-2)+(h-1))+h=2^2(2T(h-3)+(h-2))+2(h-1)+h$
.
.
.
so you get:
$$T(h)= \Sigma_{i=0}^h2^i*(h-i)$$
