Summing An Infinite Series

Today’s post will be divided into two sections, the first of which will be a geometric series lesson geared toward those that consider themselves novices in the mathematical arena followed by an application of that lesson in solving last week’s Riddler Classic. The second section is for those of you that are math nerds and problem solvers, and are interested in the solution. Please navigate accordingly.

Introduction to Summing Geometric Series

Suppose you are asked to find the following sum 1 + \frac{1}{2} + \left(\frac12\right)^2+\left(\frac12\right)^3 + \ldots

Or, what if we replaced the fraction 1/2 in the sum above to another fraction such as 1/3 or 2/7? We’ll explore one of my favorite tricks in mathematics to find such a sum.

First, let’s explore what happens if I change all the 1/2’s to 1’s. If we sum up an infinite number of 1’s we would get infinity. This would be true for all other values greater than 1 as well. However, it turns out that when you have a value between 0 and 1, let’s call it r, then the sum 1+r+r^2+r^3+\ldots will have a finite value! Let’s return to the original sum, where r = 1/2.

Since I’m after the sum and I don’t know the sum, let me create a variable S for the sum. The equation then becomes

S = 1 + \frac{1}{2} + \left(\frac12\right)^2+\left(\frac12\right)^3 + \ldots \hfill (\text{eqn. } 1)

In order to solve this equation, we will use a process called factoring, then a substitution, and then solving a relatively simple, one-variable equation. First, what if we factored out a 1/2 from every term beginning with the second:

S = 1 + \left(\frac12\right)(1) + \left(\frac12\right)\left(\frac12\right)+\left(\frac12\right)\left(\frac12\right)^2 + \left(\frac12\right)\left(\frac12\right)^3+ \ldots \hfill (\text{eqn. } 2)

Since a 1/2 can be factored out of every term beginning with the second term, we can write it

S = 1 + \frac{1}{2}(1 + \left(\frac12\right)+\left(\frac12\right)^2 + \left(\frac12\right)^3+ \ldots ) \hfill (\text{eqn. } 3)

That was the factoring step. You may be wondering why I did that. Now we can use a clever substitution. Look at equation (3) above, and in particular, the expression inside the parentheses. Does it look familiar? If we compare it to equation (1) above, you’ll notice it is the same thing! The sum we are after, S, can be written as a recursive equation involving itself! Substituting S in for the expression inside the parentheses above gives us the one variable equation S = 1 + \frac12(S).

Subtract \frac12 S from both sides and we obtain \frac12 S = 1. Now, multiplying by 2 on both sides will give S = 2.

To find that S for any fractional value between 0 or 1 (call this r) takes a similar calculation. We would end just like we did above, with the equation S = 1 + rS (where the 1/2 is now an r). If we subtract rS from both sides, we get S-rS = 1.

Now, factoring out the S on the left hand side will give you S(1-r) = 1. Finally, dividing by (1-r) on both sides gives us the general formula S = \frac{1}{1-r}.

You can now sum up infinite geometric series! Putting the final resulting formula for S in place of the original form of S gives

1 + r + r^2 + r^3 + \ldots = \frac{1}{1-r} \hfill (\text{eqn. } 4)

This equation works for all values of r in between 0 and 1. See if you can now find the sum if it were 1/3 or 2/7 now.

Probability a Bacterial Colony Will Last

Last Friday, the Riddler Classic posed a question from Adam Wagner. Here it is reprinted for convenience.

You are studying a new strain of bacteria, Riddlerium classicum (or R. classicum, as the researchers call it). Each R. classicum bacterium will do one of two things: split into two copies of itself or die. There is an 80 percent chance of the former and a 20 percent chance of the latter.

If you start with a single R. classicum bacterium, what is the probability that it will lead to an everlasting colony (i.e., the colony will theoretically persist for an infinite amount of time)?

Extra credit: Suppose that, instead of 80 percent, each bacterium divides with probability p. Now what’s the probability that a single bacterium will lead to an everlasting colony?

The Riddler, FiveThirtyEight 06/12/2020

To solve this problem, I used a rather simple formula taken from the 11th edition of Introduction to Probability Models. The following is equation (4.20) on page 236 of the text linked in the previous sentence:

\displaystyle \pi_0 = \sum_{j=0}^\infty \pi_0^j P_j \hfill (\text{eqn. } 5)

The \pi_0 represents the probability that the bacterial colony will eventually die. The P_j represents the probability that any individual cell will split into j other cells before dying.

Let’s first explore P_j. Instead of thinking of cells as splitting, think of cells as having offspring and that the right side of the split is the offspring while the left side is the parent. So, the probability that a cell will have 0 offspring (not split at all) is given as 20%. Thus, P_0 = 0.20.

The probability it will have only one offspring (split once and then die) would be P_1 = (0.8)(0.2) = 0.16 by the multiplication rule of probability. The probability it will split twice and die is P_2 = (0.8)^2(0.2). The pattern continues forever, so that the probability of splitting j times and then dying is P_j = (0.8)^j(0.2).

Now, to find the probability that the colony eventually dies out (\pi_0), we sum up the following:

  • P_0, the probability the initial cell dies right away
  • P_1 \cdot \pi_0, the probability that the initial cell has only one offspring before dying, times the probability the colony eventually dies out from this new lone cell
  • P_2 \cdot (\pi_0)^2, the probability the initial cell has two offspring before dying, times the probability the colony eventually dies out from one of those offspring times the probability the colony eventually dies out from the other offspring
  • P_3 \cdot (\pi_0)^3, and so on…

This gives us equation 5 above. Writing it out using the values we have obtained for P_j, we get

\displaystyle \pi_0  = 0.2 + 0.2(0.8\pi_0)+0.2(0.8\pi_0)^2 + 0.2(0.8\pi_0)^3 + \ldots

\displaystyle  \pi_0 = 0.2 (1+ (0.8\pi_0)+(0.8\pi_0)^2 + (0.8\pi_0)^3 + \ldots )

Using equation (4) from the first section now gives

\displaystyle \pi_0 = \frac{0.2}{1-0.8\pi_0} \hfill (\text{eqn. } 6)

This becomes the quadratic equation 4\pi_0^2-5\pi_0+1 = 0, which has the two solutions \pi_0 = 0.25 and \pi_0 = 1. The one that makes sense in this case is the first.

As 25% is the probability that the colony will eventually die out, then 75% is the probability that the colony will lead to an everlasting colony.

To address the extra credit, we replace the 0.8 in equation (6) with p and the 0.2 in equation (6) with 1-p to get \pi_0 = \frac{1-p}{1-p\pi_0}. This becomes the quadratic equation p\pi_0^2 - \pi_0 + (1-p) = 0 which has the two solutions \pi_0  = \frac{1-p}{p} and \pi_0=1 the first of which makes sense only when p > 0.5, the latter of which only makes sense when p \leq 0.5.

As \frac{1-p}{p} is the probability that the colony will eventually die out, then \frac{2p - 1}{p} is the probability that the colony will lead to an everlasting colony.

Featured photo by Franck V. on Unsplash

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s