<s>[INST] Am I properly simplifying this geometric progression? I'm studying recurrence relations and am given:
$T(n) = 2 \cdot T(n-1) - 1$
with an initial condition that $T(1) = 3$.
I worked through the first few recurrences:
$T(n-1) = 2^2 \cdot T(n-2) - 2 - 1$
$T(n-2) = 2^3 \cdot T(n-3) - 2^2 - 2 - 1$
and so forth, and came the conclusion that the pattern
$2^k \cdot T(n-k) - 2^{k-1} - 2^{k-2} - ... 2 - 1$
represents this relation. Since we have T(1) = 3, there must be some $n$ and $k$ such that $n-k = 1$, so $k= n - 1$. Substituting:
$2^{n-1} \cdot T(1) - 2^{n-2} - 2^{n-3} - ... 2 - 1$
but T(1) = 3, so...
$2^{n-1} \cdot 3 - 2^{n-2} - 2^{n-3} - ... 2 - 1$
Factoring out a $-1$ I have something that looks for all the world like a geometric progression:
$2^{n-1} \cdot 3 - (1 + 2 + ... + 2^{n-3} + 2^{n-2})$
However, I'm convinced my progression is missing a term, namely $2^{n-1}$. It's outside the progression, being multiplied by three. In my notes, my instructor simplified the progression to:
$\frac{2^{n-1} - 1}{2 - 1}$
I'm confused about where $n-1$ in the exponent of the geometric progression simplification is coming from. I eventually solve the recurrence relation as :
$3 \cdot 2^{n-1} - 2^{n-1} + 1 = 2^n + 1$
Is my understanding of the simplification of the geometric progression correct?
 [/INST] You've gotten an answer to your specific question, but I want to explain how to correctly solve the question in a mathematically rigorous manner, and not appealing to handwaving. (Every occurrence of "···" is an instance of lack of rigour.)

Working 1
$T(n) - 2·T(n-1) = -1$.
$2 · ( T(n-1) - 2·T(n-2) ) = 2·-1$.   // We do this to match and cancel the $2·T(n-1)$.
$4 · ( T(n-2) - 2·T(n-3) ) = 4·-1$.   // We do this to match and cancel the $4·T(n-2)$.
...   // Not rigorous! We need to express the pattern rigorously.
Solution 1
Take any integer $n > 1$.
$T(n) - 2·T(n-1) = -1$.
$2^k · ( T(n-k) - 2·T(n-k-1) ) = -2^k$ for every integer $k < n-1$.
$\sum_{k=0}^{n-2} ( 2^k · ( T(n-k) - 2·T(n-k-1) ) ) = \sum_{k=0}^{n-2} -2^k$.
$\sum_{k=0}^{n-2} ( 2^k·T(n-k) - 2^{k+1}·T(n-k-1) ) = \sum_{k=0}^{n-2} -2^k$.
$\sum_{k=0}^{n-2} (2^k·T(n-k)) - \sum_{k=0}^{n-2} (2^{k+1}·T(n-k-1)) = -2^{n-1} + 1$.
$\sum_{k=0}^{n-2} (2^k·T(n-k)) - \sum_{k=1}^{n-1} (2^k·T(n-k)) = -2^{n-1} + 1$.
$2^0·T(n-0) - 2^{n-1}·T(n-(n-1)) = -2^{n-1} + 1$.
$T(n) = 2^{n-1}·T(1) - 2^{n-1} + 1 = 2^n + 1$.
Check that $T(1) = 2^1 + 1$ as well, because the above proof assumed $n > 1$.

Solution 2
Take any integer $n > 1$.
$T(n) - 2·T(n-1) = -1$.
$( T(n) - 2·T(n-1) ) / 2^n = -1/2^n$.
$T(n)/2^n - T(n-1)/2^{n-1} = -1/2^n$.
Take any integer $m > 1$.
$\sum_{n=2}^m ( T(n)/2^n - T(n-1)/2^{n-1} ) = \sum_{n=2}^m -1/2^n$.
$\sum_{n=2}^m (T(n)/2^n) - \sum_{n=2}^m (T(n-1)/2^{n-1}) = -1/2 + 1/2^m$.
$\sum_{n=2}^m (T(n)/2^n) - \sum_{n=1}^{m-1} (T(n)/2^n) = -1/2 + 1/2^m$.
$T(m)/2^m - T(1)/2^1 = -1/2 + 1/2^m$.
$T(m) = 2^m·(T(1)/2-1/2) + 1 = 2^m + 1$.
Check that $T(1) = 2^1+1$ as well.
</s>