4 ms·

A quicker proof is to just differentiate. For |r| < 1, we have 1 + r + r^2 + ... = 1/(1-r) Differentiate both sides of the equation: 1 + 2r + 3r^2 +

A quicker proof is to just differentiate. For |r| < 1, we have 1 + r + r^2 + ... = 1/(1-r) Differentiate both sides of the equation: 1 + 2r + 3r^2 + ... = 1/(1-r)^2 Here's a bijective combinatorial proof, which I like best of all. It uses the concept of generating functions. As a caveat, it only shows the equality for formal power series, not analytic power series. The series 1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r. Then 1/(1-r)^2 is the type of pairs of tuples (the tuples in a pair need not have the same length). A pair of tuples can be mapped to a single tuple by concatenation. Conversely, a single tuple can be split into a pair of tuples. How many ways can this splitting be done if the tuple has length n? In n+1 ways; for example, the 2-tuple (a,b) can be split into the 3 pairs of tuples ((a,b), ()), ((a), (b)) and ((), (a, b)), which are exactly the pairs that concatenate to (a,b). Thus the bijection from 1 + 2r + ... + (n+1) r^n + ... to 1/(1-r)^2 maps an element of (n+1) r^n, which is an index 0 <= k <= n and an n-tuple, to the pair of tuples gotten from splitting that n-tuple at index k.

nodemaker 15y ago
Thanks ...the differential proof is very insightful and perhaps says something about differentiation itself. EDIT 1: Forgive my ignorance but can you please elaborate on 1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ? EDIT 2: Okay I think I get it. 1 + r + r2 are the terms in the expansion of (1+r)n
- psykotic 15y ago
  It does say something important about differentiation, which shows up very clearly and explicitly in the theory of generating functions and combinatorial species, and relates to my second proof. When you differentiate a type, you get the type of its splittings or what Conor McBride calls its one-hole contexts. > >1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ? r^n is the type of n-tuples with entries in r. When you sum over all n, you get the type of tuples of any length with entries in r. One thing that might be confusing you is that I'm thinking of r itself as a type, not as a number. You get a number from a type by counting its elements, but a type has much more structure than just its size.
- deleted 15y ago
  [deleted]
knerd83 15y ago
Thanks. That's really cool.
psykotic 15y ago
Here's yet another proof. This one uses probability theory. Let's warm up with a probabilistic proof of 1 + p + p^2 + ... = 1/(1-p) in the form (1-p)(1 + p + p^2 + ...) = 1 This says that if you have a Bernoulli process with failure probability p and success probability 1-p, you will eventually succeed with probability 1. Indeed, (1-p) p^n is the probability that you will succeed after n failures. To see this is true (it is certainly intuitively plausible), note that the probability of taking longer than n tries is p^n, which goes to zero as n goes to infinity. We can apply the same kind of reasoning to (1-p)^2 (1 + 2p + 3p^2 + ...) = 1 As before, we have a process with failure probability p and success probability p-1. However, rather than stopping after the first success, we will continue until we have two successes. Now take a look at the terms of the equation's left-hand side: (1-p)^2 (n+1) p^n This is the probability that we will have gotten 2 successes (and hence n failures) after n+2 steps. The second success must always be the final trial, so there are n+1 possible positions for the first success. That explains the factor of n+1. With that understood, the equation simply says that we will eventually get 2 successes with probability 1. To see why, note that the probability of never getting any successes in n tries is p^n as before, which tends to zero. So we will eventually get at least one success with probability 1. But once we have that first success, getting the second success is just our first problem repeated, so we know that happens eventually with probability 1. This proof technique generalizes easily. If we keep trying until we have 3 successes, we get a factor of C(n+2, 2) = (n+2)(n+1)/2 for the number of ways the first 2 successes can be placed before the third and final success when there are n failures and 3 successes. We show that a first success occurs eventually with probability 1 as before, which reduces the problem to getting two subsequent successes, a problem we already solved. You can see this yields a proof by induction for this whole class of series identities, but it's not of those unenlightening proofs by induction that shows you something is true but does not tell you why.

nodemaker 15y ago

Thanks ...the differential proof is very insightful and perhaps says something about differentiation itself. EDIT 1: Forgive my ignorance but can you please elaborate on 1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ? EDIT 2: Okay I think I get it. 1 + r + r2 are the terms in the expansion of (1+r)n

psykotic 15y ago
It does say something important about differentiation, which shows up very clearly and explicitly in the theory of generating functions and combinatorial species, and relates to my second proof. When you differentiate a type, you get the type of its splittings or what Conor McBride calls its one-hole contexts. > >1 + r + r^2 + ... = 1/(1-r) is the type of tuples with entries in r ? r^n is the type of n-tuples with entries in r. When you sum over all n, you get the type of tuples of any length with entries in r. One thing that might be confusing you is that I'm thinking of r itself as a type, not as a number. You get a number from a type by counting its elements, but a type has much more structure than just its size.
deleted 15y ago
[deleted]

knerd83 15y ago

Thanks. That's really cool.

psykotic 15y ago

Here's yet another proof. This one uses probability theory. Let's warm up with a probabilistic proof of 1 + p + p^2 + ... = 1/(1-p) in the form (1-p)(1 + p + p^2 + ...) = 1 This says that if you have a Bernoulli process with failure probability p and success probability 1-p, you will eventually succeed with probability 1. Indeed, (1-p) p^n is the probability that you will succeed after n failures. To see this is true (it is certainly intuitively plausible), note that the probability of taking longer than n tries is p^n, which goes to zero as n goes to infinity. We can apply the same kind of reasoning to (1-p)^2 (1 + 2p + 3p^2 + ...) = 1 As before, we have a process with failure probability p and success probability p-1. However, rather than stopping after the first success, we will continue until we have two successes. Now take a look at the terms of the equation's left-hand side: (1-p)^2 (n+1) p^n This is the probability that we will have gotten 2 successes (and hence n failures) after n+2 steps. The second success must always be the final trial, so there are n+1 possible positions for the first success. That explains the factor of n+1. With that understood, the equation simply says that we will eventually get 2 successes with probability 1. To see why, note that the probability of never getting any successes in n tries is p^n as before, which tends to zero. So we will eventually get at least one success with probability 1. But once we have that first success, getting the second success is just our first problem repeated, so we know that happens eventually with probability 1. This proof technique generalizes easily. If we keep trying until we have 3 successes, we get a factor of C(n+2, 2) = (n+2)(n+1)/2 for the number of ways the first 2 successes can be placed before the third and final success when there are n failures and 3 successes. We show that a first success occurs eventually with probability 1 as before, which reduces the problem to getting two subsequent successes, a problem we already solved. You can see this yields a proof by induction for this whole class of series identities, but it's not of those unenlightening proofs by induction that shows you something is true but does not tell you why.