My class and I were introduced to recurrences last week, and we took up this example (see link) in class. Unfortunately I find it really tricky still, and I apologize in advance if this question is...pathetic(?)
From the steps shown class, solving it starts with finding a pattern:
T(n) = 2T(n-1) + 1
=2[2T(n-2) + 1] + 1
=4[2T(n-3) + 1] + 3
=8[2T(n-4) + 1] + 7
I (believe I) understand why 2T(n-1) + 1 is in the square brackets. But I have no idea where the 2, 4, 8 (in the beginning of each) comes from, as with the 1, 3, 7 and the ends.
Anyone would be a life saver to shed some light on this, so I can continue on with practicing and solving other recurrences.