A formula for the total number of biological ancestors for a given number of generations back in history

We seek to derive a formula for an individual’s total number of biological ancestors for a given number of generations back.  Beginning, we observe that at one generation back, there are two biological parents.  Each biological parent has two biological parents which are the original individual’s biological grandparents.  With this in mind, it is intuitively obvious that there are 2ⁿ biological ancestors of the original individual at each generation where n is the number of generations back for that particular generation.

However, the total number of biological ancestors is the sum of the number of biological ancestors at each generation level down through the original individual’s biological parents.  So, the total number of biological ancestors is of the form 2¹ + 2² + … + 2ⁿ, where n is the number of generations back.  If one examines the value of this expression for the first several positive integer values of n, it begins to appear as if the value equates to the expression 2ⁿ⁺¹ - 2.

Can we prove the following?

2ⁿ⁺¹ - 2 = 2¹ + 2² + … + 2ⁿ, where n is a positive integer

We begin by adding 2 to both sides of the equation

2ⁿ⁺¹ = 2 + 2¹ + 2² + … + 2ⁿ

Now we divide both sides by 2

2ⁿ = 1 + 2⁰ + 2¹ + … + 2^n-1

Now we subtract 1 from both sides

2ⁿ – 1 = 2⁰ + 2¹ + … + 2^n-1

An inductive proof of the above equation does exist for all positive integers n, and I will now attempt to explain it as fully as I am able.

To inductively prove an equation in the variable n, one must do two things: 

1)    One must show that the equation is true for the lowest value of n for which we expect the equation to be true.  In this case, we don’t even care whether the equation is true for values of n less than 1 or for any values of n which are not integers.  Therefore, for this step we will establish that the equation is true for n=1.

2)    After step 1, we must then show that if the equation is true for some specific integer value of n (we will call this specific value k), then the equation is also true for the very next larger integer value of n (which we will call k + 1).  It is important to note that step 2, which we are now discussing, does not prove (or try to prove) that the equation is true for n=k.  We are trying to prove that if the equation is true for n=k, then it is true for n=k+1.  This accomplishes something useful, because if we successfully completed step 1, then we verified with arithmetic that the equation was true for n=1.  Well, remember we never said what k was equal to.  One of the possible values of k could be 1.  So, if we complete step 2, we’ve shown that if the equation is true for n=1, then it’s also true for n=2.  And if it’s true for n=2, then it’s also true for n=3, and so forth.  Our focus must be on how to conceptualize this “if…then” scenario.  But first, let’s just get step 1 out of the way.

Let’s restate our altered version of the equation that I said we could prove:

2ⁿ – 1 = 2⁰ + 2¹ + … + 2^n-1

For n=1,

2¹ - 1= 2^1-1

Before we evaluate this and see if the two sides are equal, I want to address any confusion which may have arisen.  I admit that the equation
2ⁿ – 1 = 2⁰ + 2¹ + … + 2^n-1 seems to imply that the right hand side will be the sum of at least three terms.  For n=3, it would consist of three terms.  But we’ve got n=1, so let’s consider what the expression 2⁰ + 2¹ + … + 2^n-1 is really saying.  Translated from the language of mathematics into the English language it says, “the sum of every nonnegative integer power of 2 up to n-1”.  Since we are dealing with n=1, then n-1=0.  So we read that again as, “the sum of every nonnegative integer power of 2 up to 0”.  This means from 2⁰ all the way up to 2⁰.  That means just a simple 2⁰.  Returning to our arithmetic, we write the next step as

2 – 1 = 2⁰

or

1 = 1

Step 1 of the inductive proof has been a success.

Turning our attention to step 2, consider the following sentence:

“If there is an elephant in the room, the floor has undergone excessive stress.”

We can prove this statement by researching the weight of elephants, and by determining the stress which would be considered excessive for the floor.  If we do find that the weight of an elephant would place excessive stress on the floor, then the statement is true, even if there never has been and never will be an elephant in the room.  Metaphorically speaking, we have determined that A implies B.  We never said that A was true.  We never said that B was true.  We only said, “If A, then B.”  The word “if” allows our sentence to be true, even though it may be hypothetical.  Nevertheless, if we ever could prove A then we’ve proved B, keeping in mind that earlier we did prove that A implies B.

We have an equation

2ⁿ – 1 = 2⁰ + 2¹ + … + 2^n-1

We haven’t proved the equation yet, but the “equation” as written may have implications.  It may be able to imply something for us.

Referring back to our preview of step 2, we proceed by rewriting the above equation for n=k and n=k+1:

For n=k

2^k – 1 = 2⁰ + 2¹ + … + 2^k-1

and for n=k+1

2^k+1 – 1 = 2⁰ + 2¹ + … + 2^k-1 + 2^k

Note that the terms in red above are, according to our equation for case n=k, equal to 2^k – 1.  So we may write

2^k+1 – 1 = 2^k – 1 + 2^k

2^k+1 – 1 = 2(2^k) – 1

2^k+1 – 1 = 2^k+1 – 1

Now we have shown that case n=k implies case n=k+1.  Earlier in step 1 we showed that the equation is true for n=1, so it stands to reason that the equation of case n=k is true for k=1.  And if that equation is true for n=k=1, it is also true for n=k+1=2.  Furthermore, the fact that case n=k implies case n=k+1 means that case n=k+1 implies case n=k+1+1, etc.  Step 2 is a success.  We have proved that the original equation is true for all positive integers.  The total number of biological ancestors for n generations back in history is given by the expression

2ⁿ⁺¹ - 2