Am I properly simplifying this geometric progression?

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.


The left sides of your second and third equations should be $T(n)$, not what you have written. Under "Factoring out a $-1$" it would be better to end with $2^{n-3}+2^{n-2}$ to maintain the pattern of the exponents increasing by $1$. Your progression does end with $2^{n-2}$. That is why the numerator of the sum has $2^{n-1}$. If you look at the formula for the sum of a finite geometric progression, the exponent is $1$ more than the highest term: $$1+r+r^2+\ldots +r^k=\frac {r^{k+1}-1}{r-1}$$ When you add $1$ to $n-2$ you get $n-1$ so your teacher's sum of the progression is correct. Your final answer is also correct.