0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That is exactly what I was looking for, but like I said not all series adhere to that form. What other formulas are common in geometric series or do I use the derivation that you used as a basis for all series? $\endgroup$ – Code4life Apr 29 '19 at 0:24
  • $\begingroup$ Unfortunately there are not in general formulas like this for series except for arithmetic or geometric series. The advice I give to you is to solve as much you can lots of exercises involving series. After that you will get lots of tools to tackle some series. $\endgroup$ – DINEDINE Apr 29 '19 at 0:30
  • $\begingroup$ Alright thanks but here is another example: imgur.com/qtbzfID. It's essentially analogous to the previous iterative substitution but the sequence is recurring on the denominator instead. $\endgroup$ – Code4life Apr 29 '19 at 0:47
  • $\begingroup$ It is always a geometric series with $x=\frac13$ $\endgroup$ – DINEDINE Apr 29 '19 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.