Could you please check if this substitution is right so far?

Question

The question:

Use resubstitution to solve the following recurrence equation:

T(N) = 2T(n-1) + n; n >=2 and T(1) = 1

So far I have this:

T(n) = 2T(n-1) + n

= 2(2T(n-2) + (n-1)) + n

= 4T(n-2) + 3n -2

= 2(4T(n-3) + 3(n-1) -2) + n

= 2(4T(n-3) + 3n -3 -2) + n

= 2(4T(n-3) + 3n -5) + n

= 8T(n-3) + 6n - 10 + n

= 8T(n-3) +7n -10

I'm just wondering if so far, the way I'm approaching this is correct. Any help is appreciated, thank you.

Answer 1

This step is wrong:

= 4T(n-2) + 3n -2

= 2(4T(n-3) + 3(n-1) -2) + n

It should be

= 4T(n-2) + 3n -2

= 4(2T(n-3) + (n-2)) + 3n - 2

You replace the T(n-i) by 2T(n-i-1) + (n-i).

Apart from that, I think you're getting this wrong. What your teacher wants you to do, is to feel what the value of T(n) will be. In this case, you see that each time you iterate, you multiply the first coefficient by 2, and you have at the end a member like an+b. This means that T(n) = 2^n + O(n) because only the biggest member matters.