Solving $T(n) = 2^n T(n-1) + 2^n$ Is there an exact (and if not, an asymptotic) solution to the following recurrence relation?
$$
T(n) = 2^n T(n-1) + 2^n, \text{for } n > 0
$$
If yes, I'd also like to know whether this relation is an instance of a more general class of relations for which you can apply the same technique for solving it.

A sketch:

*

*Let $u_n$ denote the value of $T(n)$ obtained if $T(0)=0$. Prove by induction $T(n)=2^{n(n+1)/2}T(0)+u_n$.


*Define $v_n:=u_n/2^{n(n+1)/2}$ so $T(n)=2^{n(n+1)/2}(T(0)+v_n)$. Prove by induction $v_n=v_{n-1}+2^{-n(n-1)/2}$.


*Since $v_0=0$, $T(n)=2^{n(n+1)/2}(T(0)+\sum_{k=1}^n2^{-k(k-1)/2})$.
