I have the following equation: $$g(n) = 1 + c^2 + c^3 + ... + c^n$$ The closed form solution of this series is $$g(n) = \frac{c^{n+1} -1}{c-1}$$
However, I am having a difficult time seeing the pattern that leads to this. $$ n =0 : 1 $$ $$ n =1 : 1 + c $$ $$ n = 2 : 1 + c + c^2 = 1 + c(1+c)$$ $$ n =3 : 1 + c(1+ c(1 + c))$$
Can someone provide some insight here?
$\endgroup$3 Answers
$\begingroup$The summation formula is: $$\sum_{i=1}^n a_i = a \frac{(1 - r^n)}{(1 - r)}$$
Rearranging the terms of the series into the usual "descending order" for polynomials, we get a series expansion of:
$$ar^{n–1} + ar^{n–2} + \ldots + ar^3 + ar^2 + ar + a$$
A basic property of polynomials is that if you divide $x^n – 1$ by $x – 1$, you'll get:
$$x^{n–1} + x^{n–2} + \ldots + x^3 + x^2 + x + 1$$
That is:
$$x^{n-1} + \ldots + x^2 + x + 1 = \frac{(x^n - 1)}{(x - 1)}$$
Applying the above to the geometric summation (and reversing both subtractions, so the value of that last fraction isn't changed), we get:
$$ar^{n–1} + ar^{n–2} + \ldots + ar^3 + ar^2 + ar + a$$
$$= a(r^{n–1} + r^{n–2} + \ldots + r^3 + r^2 + r + 1)$$
$$= a \frac{(1 - r^n)}{(1 - r)}$$
The above derivation can be extended to give the formula for infinite series, but requires tools from calculus.
For now, just note that, for $|r|<1$, a basic property of exponential functions is that $r^n$ must get closer and closer to zero as $n$ gets larger.
Very quickly, $r^n$ is as close to nothing as makes no difference, and, "at infinity", is ignored. This is, roughly-speaking, why the $r^n$ is missing in the infinite-sum formula.
$\endgroup$ $\begingroup$Let $S=1+c+c^2+...+c^n$ then $c.S=c+c^2+...c^{n+1}$, subtract them.
$\endgroup$ $\begingroup$Turn it around by multiplying both sides with $c-1$ and then calculate $$(c-1)\sum_{k=0}^n c^k$$
This is a telescoping sum where only the end points of the sum survive and all the mid terms cancel out. Each new c multiplied will be removed at the next k in the sum (except for the last).
$\endgroup$
