Counting Bug Populations

Date: 12/03/98 at 09:04:16
From: Naveed Ahmed
Subject: Probability, sequences, formulas

We are given the following information:

   A happy bug splits into a sad bug and a blank bug.
   A sad bug splits into 2 happy bugs.
   A blank bug splits into a sad bug and a happy bug.

   The generation starts off with 1 happy bug which splits and forms 
   the 2nd generation.

   The bugs die when they split.
   The bugs live the same amount of time.

I have worked the first five generations to find how many of each kind 
of bugs there are, but I can't find the formula for the nth generation. 
Could also you tell me the formulas if the first generation starts with 
a sad bug and a blank bug?

Thanks.

Date: 12/03/98 at 11:39:23
From: Doctor Anthony
Subject: Re: Probability, sequences, formulas

The first step is to make a table, using the following notation:
n = generation, H = happy bug, S = sad bug, and B = blank bug.

     n   1   2   3   4    5    6    7    8     9   10     11    12  
   ----------------------------------------------------------------
     H   1   0   2   2    6   10   22   42    86   170   342   682  
     B   0   1   1   3    5   11   21   43    85   171   341   683  
     S   0   1   1   3    5   11   21   43    85   171   341   683  
   -----------------------------------------------------------------
   Total 1   2  2^2 2^3  2^4 2^5  2^6   2^7  2^8   2^9   2^10  2^11  

The pattern shows H is one more and one less alternatively than B and 
S as we move up the generations. The total for the nth generation is 
always given by 2^(n-1). Also each of H, B and S is close to 1/3 of 
the total for any generation. To take account of the pattern we can 
give two formulae depending on whether n is even or odd. A little 
juggling shows the following is the pattern:

          n EVEN                      n ODD
         ---------                 -----------
    
         2^(n-1)- 2                2^(n-1)+ 2
   H =  -----------          H  = ------------
             3                          3

             2^(n-1)+ 1                2^(n-1)- 1
   B and S = ----------      B and S = ------------  
                 3                         3

If you start with a first generation of S + B, you get the same table 
as above except that n-1 is replaced by n. So the new formulae can be 
produced by using n instead of n-1 and swapping over the n = even and 
n = odd labels:


         n ODD                   n EVEN
      -----------            ---------------

        2^n - 2                  2^n + 2
   H = ---------           H =  ----------
            3                        3

              2^n + 1                 2^n - 1
   B and S =  --------     B and S = ---------   
                 3                      3

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/