0

I was trying to derive the sum of a geometric progression: $$\sum_{i=0}^{n-1}{ar^i}$$ This is equal to: $$ar^0+ar^1+ar^2+\cdots+ar^{n-1}$$ Factorising with $a$, I get: $$a \sum_{i=0}^{n-1}{r^i}$$

Assuming $r$ is $6$ for example, I get: $$a\left[r^0(1+r(1+r(1+r(1+r(1+r)))))\right]$$ The number of $(1+r)$s inside is equal to $n-1$.

I have no idea how to expand the above equation, and simplify it.

Can someone please give me a step-by-step expansion and simplification of the equation. Something a $9^{th}$ grader would understand.

EDIT
In general, I don't understand how to expand nested braces(recursion isn't the most intuitive thing for me) so a very simple explanation of how this is done will be much appreciated.

Tobi Alafin
  • 1,187

4 Answers4

3

Call

$$ S = \sum_{i = 0}^{n-1}ar^i = a + ar + ar^2 + \cdots + ar^{n-1} \tag{1} $$

if you multiply both sides by $r$ you get

$$ r S = ar + a r^2 + ar^3 + \cdots + ar^n \tag{2} $$

When you subtract Eq. (1) from Eq. (2) you will see that most terms cancel out

\begin{eqnarray} S - rS &=& S(1- r) = (a + ar + ar^2 + \cdots + ar^{n-1}) - (ar + ar^2 + ar^3 + \cdots + ar^n) \\ &=& a - ar^n = a(1 - r^n) \end{eqnarray}

So that

$$ S = a \frac{1 - r^n}{1 - r} \tag{3} $$

Therefore

$$ \sum_{i=0}^{n-1} ar^i = a \frac{1-r^n}{1 - r} ~~~~~\mbox{if}~~~r\ne 1 $$

caverac
  • 19,345
  • Thanks for the answer :) However, I would *really* appreciate it if you 'completed' my derivation. I purposedully did not Google the answer. – Tobi Alafin Dec 15 '16 at 18:08
  • @TobiAlafin Probably I misunderstood you, my apologies. But if you expand $a(1 + r(1 + r(1 + \cdots ))$ you are going to get back $a + ar+ ar^2 + \cdots$ – caverac Dec 15 '16 at 18:22
  • P.S you have a small typo at the end of your answer. Too small for edit. – Tobi Alafin Dec 15 '16 at 18:32
3

Using the difference of powers identity:

$$ a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2 + \cdots + a b^{n-2}+b^{n-1}) $$

with $\,a=1, b=r\,$ gives $\;1-r^n=(1-r)(1+r+\cdots+ r^{n-1})\;$ therefore:

$$ 1+r+\cdots+r^{n-1} = \cfrac{1-r^n}{1-r} $$

dxiv
  • 76,497
  • Such a succint proof. – Tobi Alafin Dec 16 '16 at 06:40
  • In the end, the difference of powers identity and the sum of a geometric progression formula are equivalent, modulo some simple algebraic manipulation. Guess it comes down to which one you learned first, and are more at ease with. – dxiv Dec 16 '16 at 06:57
3

Without words:

$$\begin{align}S=&a+ar^1+ar^2+...\ \ \ \ \ \ \ ar^{n-1}\\ rS=&\ \ \ \ \ \ \ ar^1+ar^2+ar^3+...\ \ \ \ \ \ \ \ \ ar^{n}\end{align}$$

$$rS-S=ar^n-a$$ $$S=a\frac{r^n-1}{r-1}$$

0

The following recurrence should be obvious:

$$S_{n+1}=rS_n+a,$$ with $S_0=0$.

We can solve it by the theory of linear recurrences. The solution is made of an homogeneous part, such that

$$H_{n+1}=rH_n,$$ i.e. $$H_n=Cr^n$$

and a particular non-homogenous part,

$$N_{n+1}=rN_n+a$$ that is fulfilled by a constant,

$$N=rN+a,$$ or

$$N=\frac a{1-r}.$$

The other constant is obtained from the initial condition and

$$S_0=H_0+N_0=C+N=0.$$

Putting all pieces together,

$$S_n=\frac a{1-r}-\frac{a}{1-r}r^n.$$

In the special case that $r=1$, the recurrence is

$$S_{n+1}=S_n+a$$ and the solution obviously $$S_n=an.$$