Solve The Recurrence Relation

Question

T(n) = 1,                         if n = 1

       = T(n-1) + 2^n          , otherwise

Answer 1

       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)

Comments

Thanks. Answer is 2^(N+1)-1 but How do you come up to second line? I do not understand how to proceed?