T(n) = T(n-1) + 2^n
= T(n-2) + 2^(n-1) + 2^n
= T(n-3) + 2^(n-2) + 2^(n-1) + 2^n
..........
..........
..........
= T(n-k) + 2^(n-(k-1)) + 2^(n-(k-2)) + ............................. + 2^n
Take k = n-1
= T(1) + 2^(2) + 2^3 + 2^4 + ........................ + 2^n
= 1 + 2^2 + 2^3 + 2^4 + .......................... + 2^n
= 2^1 + 2^2 + 2^3 + ................................ + 2^n - 1
= 2^(n+1) - 1
= O(2^n)