Is there a simple enough formula for this geometric series problem?

Question

A friend of mine has recently started a challenge in which he starts by doing 22 pressups and then nominates somebody else to do 22 pressups the next day. This continues every day in which those who have not exceeded 22 nominations (22 days) continue to do their pressups and make their nominations.

What is the geometric formula for this progression? This assumes no one asks the same person twice and everyone accepts their nomination. Additionally how long before the number of people involved will exceed the population of the Earth at ~7.4 billion?

This begins as a simple 2^n progression however after the 22nd day it gets complicated as my friend is no longer involved, and those that have exceeded their 22 day period no longer participate.

Ideally I would like to say how many people will be doing pressups on day 50/60/70 etc, is it possible to derive a formula that I can plug these number into to work this out? It would be easy to create a program to compute this but I wondered if it could be worked out by simple pen and paper and perhaps a calculator alone.

Answer 1

This can be modeled with a linear recurrence.

The first person to begin starts on Day $1$, which means we can treat him as if he were nominated on Day $0$, since anyone who is nominated begins the challenge starting the following day.

Let $T(n)$ be the number of people participating on day $n$ (i.e. the number of people who are doing pressups / giving out nominations on that day):

$$T(n) = \sum_{k=1}^{22} T(n-k)$$

Base cases: $T(n)=0$ for $n<0$, $T(0) = 1$, and $T(n) = 2^{n-1}$ for $1 \leq n \leq 22$.

This is similar to the Fibonacci sequence, except instead of degree $2$, it's degree $22$.

Day $34$ is when the total number of participants exceeds the planet's population, at $T(34) = 8589921280$.

Here is a table of results:

\begin{array} {|r|r|} \hline n &T(n)\\ \hline 1 & 1 \\ \hline 2 & 2 \\ \hline 3 & 4 \\ \hline 4 & 8 \\ \hline 5 & 16 \\ \hline 6 & 32 \\ \hline 7 & 64 \\ \hline 8 & 128 \\ \hline 9 & 256 \\ \hline 10 & 512 \\ \hline 11 & 1024 \\ \hline 12 & 2048 \\ \hline 13 & 4096 \\ \hline 14 & 8192 \\ \hline 15 & 16384 \\ \hline 16 & 32768 \\ \hline 17 & 65536 \\ \hline 18 & 131072 \\ \hline 19 & 262144 \\ \hline 20 & 524288 \\ \hline 21 & 1048576 \\ \hline 22 & 2097152 \\ \hline 23 & 4194303 \\ \hline 24 & 8388605 \\ \hline 25 & 16777208 \\ \hline 26 & 33554412 \\ \hline 27 & 67108816 \\ \hline 28 & 134217616 \\ \hline 29 & 268435200 \\ \hline 30 & 536870336 \\ \hline 31 & 1073740544 \\ \hline 32 & 2147480832 \\ \hline 33 & 4294961152 \\ \hline 34 & 8589921280 \\ \hline 35 & 17179840512 \\ \hline 36 & 34359676928 \\ \hline 37 & 68719345664 \\ \hline 38 & 137438674944 \\ \hline 39 & 274877317120 \\ \hline 40 & 549754568704 \\ \hline \end{array}

Python 2.x script:

DEGREE = 22 

cache = {}

def T(n):
    if n<0:
        return 0
    if n==0:
        return 1
    if n in cache:
        return cache[n]
    cache[n] = sum(T(n-k) for k in xrange(1, DEGREE+1))
    return cache[n]

for n in xrange(1, 41):
    print "n = %s, T(n) = %s" % (n, T(n))

Answer 2

One way to approach this is through generating functions.

Let $a_n$ be the number of people participating on day $n$, starting with 1 person on day one ($a_0=1$) who participates on days 0,...,21, and who invites 22 new participants who start on days 1,...,22.

We represent this sequence $a_n$ through a generating function: $A(x)=\sum_{i=0}^\infty a_n x^n.$ This is just a formal power series, so we don't even require that it converge, although it will in our case.

Now, the first person participates on days 0,...,21, which contribute the sum $1+x+\cdots+x^21$ to $A(x)$. The person invited to start on day $k=1,\ldots,22$ will start a new chain of invitation, leading to $a_n$ participants on day $k+n$, which contributes $x^kA(x)$ for each $k$. So this makes the total $$ A(x)=(1+x+\cdots x^{21})+(x+\cdots+x^{22})A(x) =\frac{1-x^{22}}{1-x}\cdot(1+xA(x)) $$ which solves to $$ A(x)=\frac{1-x^{22}}{1-2x+x^{23}}. $$ If we rewrite this as $A(x)\cdot(1-2x+x^{23})=1-x^{22}$, we get $a_n=2^n$ for $n=0,\ldots,21$, $a_{22}=2^{22}-1$ as the first participant leaves, and thereafter we get $a_n=2a_{n-1}-a_{n-23}$.

In the long run, I would expect $a_n\sim C\cdot 1.999999762^n$ based on the roots of $1-2x+x^{23}$ (haven't checked this properly).