Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Nice Proof of a Geometric Progression Sum (sputsoft.com)
20 points by nreece on Aug 22, 2009 | hide | past | favorite | 8 comments


For this proof to be complete, it needs to be shown that the trapezoid sequence fills ABC triangle in its entirety. I.e. that for every point between A and C there is a trapezoid in the sequence that covers it. Not hard to do by any means, but the resulting proof is not going to be purely visual anymore.


Why is this completely necessary? What would be an acceptable proof to you of this statement?


Neat illustration, but I'd present the proof to kids in the usual manner:

(1 - r)(1 + r + r^2 + ... + r^n) = 1 - r^(n + 1), because all other terms cancel out.

If |r| < 1, the right part tends to 1, QED.


I can never be quite sure that I'm remembering the proper closed form expression, so I always rederive it in a way that's basically what you have here, but a little less dense:

Call the sum of the terms Sn, though we don't know what it is.

Sn = 1 + r +r^2 + . . . + r^n

Multiply each side by r

(Sn)(r) = r + r^2 + . . . + r^(n+1)

Subtract the former from the latter

Sn - (Sn)(r) = 1 - r^(n+1)

Sn(1 - r) = 1 - r^(n+1)

Sn = (1 - r^(n+1)) / (1 - r)

And there we have the closed form expression for Sn. As n goes to infinity, it approaches 1 / (1-r)


This is the correct way to prove the summation. Although, I would point out that for r > 1, it's probably better to phrase it as ( r^(n+1) - 1)/(r-1). However, it's important to note that this is only true from a series starting from zero. For a series starting from m it is:

  (r^(n+1)-r^m)/(r-1)
Which is trivially deducible from your method or the parent's method. For some reason I tend to dislike geometric proofs. This is probably because I find it very easy to make proof fallacies visually, more so than symbolically. However, this geometric proof is also less useful than the symbolic because it is much harder to use it to prove the summation at values smaller than infinity, whereas the symbolic works just as well for n.


I find this kind of post on HN very enjoyable. Thanks for sharing.


Is this the reason it is referred to as a Geometric progression?


Sort of. The way I was taught, a progression is called arithmetic because each term is the arithmetic mean of its predecessor and successor, i.e. if A comes before a term X and B comes after a term X in an arithmetic sequence, then X = (A+B)/2. Similarly, a geometric progression uses the geometric mean, i.e. X = (AB)^(1/2).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: