Recurrence Equations Can someone explain how that Tn = 2Tn-1 + 1 sequence actually works? 

The recurrence sequence is a sequence that each term is defined by its previous terms. Hence, the sequence must have the initial term. For example,
$T_n=2T_{n-1}+1.$ Assume that the sequence begin at $T_1.$
So, $T_2=2T_1+1$,
$T_3=2T_2+1=2(2T_1+1)+1=4T_1+3$ and so on.
We can see that if we do not know the value of $T_1$, we also can not find the value 
of $ T_2,T_3,...$ 
In fact, we can define recurrence relation that T_n is defined by T_{n-2}. For example,
$T_n=T_{n-2}+1$.
But in this case, the initial values must have 2 terms(T_1 and T_2).
If you want to find $T_{1000}$ of a recurrence sequence, you have to find $T_{999},T_{998},...$. It is not difficult, but it takes so much time. So, how can we find $T_{1000}$ without finding $T_{999}, T_{998},...$? That is the goal of recurrence equation.
