# How can I determine the form of a geometric series in a recurrence relation by using iterative substitution?

This question is based more in computer science however I think a mathematics approach is probably better. When solving a recurrence relation using iterative substitution you generally need to find the pattern of the constant function to the right of $$T(\frac{n}{2})$$. The sequence usually forms a geometric series and I'm supposed to simplify it to find the solution of the recurrence equation. However, I'm not sure how to do that. Some of them are not as obvious as this for example:

$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

Here is an example: iterative substitution

As you can see, the geometric series turns into $$3^i - 1$$, but why not $$2\cdot3^i$$? I'm sure my professor used some sort of formula from the geometric series like the basic one I showed above.

He just use this: $$1+x+x^2+...+x^{n-1}=\frac{x^n-1}{x-1}\ \quad\forall x\ne 1\quad\forall n\ge 1$$ A simple derivation can be: $$(x-1)(1+x+x^2+...+x^{n-1})=x+x^2+...+x^{n-1}+x^n-1-x-...-x^{n-1}=x^n-1$$
• It is always a geometric series with $x=\frac13$ – DINEDINE Apr 29 '19 at 0:50