What will be T(n) after second step in a Recurrence Relation [closed]

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

Using back Substitution at first step we get

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

If i go further one more step then what i am getting is

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

closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, fade2black, Kyle JonesNov 22 '17 at 19:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• So what is your question? – Yuval Filmus Nov 21 '17 at 14:47
• The value of T(n) which i got after 2nd step is not correct. I assume i am doing something wrong while substituting but i am unable to figure out where i am going wrong while solving the recurrence. – JobLess Nov 21 '17 at 14:51

Let's consider a simpler recursion:

$$T(n) = T(n-1).$$

Using back substitution, we get $T(n) = T(n-2)$, $T(n) = T(n-3)$, $T(n) = T(n-4)$, and so on.

What you do is go first to $T(n) = T(n-2)$, and then substitute this equation into itself to get $T(n) = T(n-4)$. So you're skipping a step.

What you get is correct, but you haven't gone further one more step, but two more steps.

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

First :

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

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

Second :

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

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

Third :

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

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

• Oh so for finding T(n-2) we have to sub it in original Equation...so what i was doing is substituting in equation that i got in 1st step.. Thanks you made it very clear... – JobLess Nov 21 '17 at 15:41
• What you did is correct, it's also possible to substitute directly in equation of 1st step, but you won't get T(n - 3). The original equation defines T(n) by T(n - 1), but the other defines T(n) by T(n - 2). With the first, you can get every term that you want. By with the second, you'll only reach terms accessible by substracting 2 to n. – user80502 Nov 21 '17 at 15:54
• Ok... So i was directly jumping and skipping some terms in between....i got it ...Thanks for helping.. Thank you Very Much – JobLess Nov 21 '17 at 16:06