Am I properly simplifying this geometric progression?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

If you are not sure that your calculation is right you should try to verify your calculations.

The first ten numbers of the first recurrence relation

$$T(n) = 2*T(n-1) - 1$$

are

$$3,5,9,17,33,65,129,257,513,1025$$

ten numbers of the second recurrence relation

$$T(n-1) = 2^2*T(n-2) - 2 - 1$$

are

$$3,9,33,129,513,2049,8193,32769,131073,524289$$

So these are different calculations, so something went wrong.

---

The sentence "the pattern ... represents this relation" is rather unclear. Give it a precise meaning and try to verify it.