Solving Recurrences 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. 
 A: What's happening here is that the recurrence relation is being applied, repeatedly.
We start off, for some $n$, with the fact that
$$\tag{1}
T(n)=2T(n-1)+1.
$$
But, we know that $T(n-1)=2T(n-2)+1$; plugging this in to $(1)$ yields
$$\tag{2}
T(n)=2(2T(n-2)+1)+1=2^2T(n-2)+2+1.
$$
But, we know that $T(n-2)=2T(n-3)+1$; plugging this in to $(2)$ yields
$$\tag{3}
T(n)=2^2(2T(n-3)+1)+2+1=2^3T(n-3)+2^2+2+1.
$$
Let's do one more: we know that $T(n-3)=2T(n-4)+1$, so that
$$
T(n)=2^3(2T(n-4)+1)+2^2+2+1=2^4T(n-4)+2^3+2^2+2+1.
$$
Do you see a pattern?  It certainly looks like for any $k<n$, we have
$$
T(n)=2^kT(n-k)+(2^{k-1}+2^{k-2}+\cdots+2+1).
$$
IF this expression is true, then in particular taking $k=n-1$ yields
$$
\begin{align*}
T(n)&=2^{n-1}T(n-(n-1))+(2^{n-2}+2^{n-3}+\cdots+2+1)\\
&=2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1)\\
&=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2+1,
\end{align*}
$$
because $T(1)=1$ by definition. Now, this is a geometric sum and can be simplified to give a nice, closed-form formula for $T(n)$.
A: $$T(n)=2T(n-1)+1\iff T(n)+1=2[T(n-1)+1]$$
Set $\displaystyle T(n)+1=U(n)\implies U(n)=2U(n-1)$ and $U(1)=\cdots$
$\displaystyle\implies U(n)=2^rU(n-r) $ for $1\le r<n$
A: It might have helped if they had shown some intermediate steps:
$$\begin{align}
T(n)&=2T(n-1)+1\\
&=2[2T(n-2)+1]+1\\
&=4T(n-2)+3\quad\text{(intermediate step)}\\
&=4[2T(n-3)+1]+3\\
&=8T(n-3)+7\quad\text{(intermediate step)}\\
&=8[2T(n-4)+1]+7\\
&=16T(n-4)+15\quad\text{(intermediate step)}\\
&\vdots
\end{align}$$
Each intermediate step just expands and collects what's on the line above it.
