

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Yesterday, a question was posted that went along the lines of:

Suppose we have a number of workers, $N$. These workers work at a constant rate of $R$ widgets per unit time. ($R > 0$) We also have a fixed time interval, $I > 0$ (in units of time), such that after $I$ time units, we add another worker.

Is there a closed form for the number of widgets produced, $W$, after $t$ time units pass? ($t$ is not necessarily a multiple of $I$.)

Unfortunately, this question was deleted (by the author) shortly following its posting. (I don't know the circumstances of why the question was deleted. If it's an open contest problem or something, I can remove this question as well--just let me know.)

I solved the problem given above after looking at the graph of output versus input. However, my solution relies on the time interval $I$ being constant. (See my work below.)

My question is, if $I$ were to vary by some rule, could a closed form be found? For example, could a solution be found if we were to add one worker every $F_n$ time-units? (where $F_n$ is the $n$th Fibonacci number)

My work for the old question:

Essentially, at $t = kI$, $k\in\mathbb{N}$, we have: $$W = \left(\frac{k(k+1)}{2}\right)IR = \left(\frac{\frac{t}{I}\left(\frac{t}{I}+1\right)}{2}\right)IR$$ This is because our "overall rate" (rate for all the workers) is $R$ for the first $I$ time-units, $2R$ for the next $I$ time-units, etc. The total output for the first $k$ intervals is the sum of these overall rates times $I$. This is equivalent to the sum of the first $k$ natural numbers times $IR$

At $t$ between multiples of $I$, we simply use the amount at the previous multiple of $I$ and add to it the amount of widgets produced since then: $$W = \left(\frac{\left\lfloor\frac{t}{I}\right\rfloor\left(\left\lfloor\frac{t}{I}\right\rfloor+1\right)}{2}\right)IR + \left(\left\lfloor\frac{t}{I}\right\rfloor + 1 \right)\left(t-\left\lfloor\frac{t}{I}\right\rfloor I\right)R$$

(I haven't paid attention to the units of the above expressions. They work out numerically, but not with respect to their units.)

share|cite|improve this question
up vote 1 down vote accepted

Let $f(n)$ be the number of units of time that pass before the $n$th worker is added, and define $f(0) = 0$. That is, at time $f(0)$ there are $N$ workers, at time $f(1)$ there are $N+1$ workers, and so on. Then the number of widgets produced up to time $f(n)$ is \begin{align*} &\sum_{i=0}^{n-1} \#\{\text{Widgets produced between $f(i)$ and $f(i+1)$}\} \\ = &\sum_{i=0}^{n-1} [f(i+1) - f(i)] \cdot [ N + i ] \cdot R \\ = &\sum_{i=0}^{n-1} Ri[f(i+1) - f(i)] + \sum_{i=0}^{n-1} RN [f(i+1) - f(i)] \\ = &\sum_{j=1}^n R(j-1) f(j) - \sum_{j=1}^{n-1} R j f(j) + \sum_{j=1}^{n} RN f(j) - \sum_{j=1}^{n-1} RN f(j) \\ = &(n-1) R f(n) - R \sum_{j=1}^{n-1} f(j) + RN f(n) \\ = &\boxed{R \left[ (N + n) f(n) - \sum_{j=1}^{n} f(j) \right]}. \end{align*} As a check that this formula is right, note it satisfies certain edge cases: $n = 0$ correctly gives $0$, and $f(n) = In$ starting with one worker at the start ($N = 1)$ gives your expression $IR \frac{n(n+1)}{2}$.

Philosophically one may debate about whether a summation counts as a "closed form", but it is clear that in the case of a general $f$ there is no simpler expression.

When $f(n)$ is the $n$th Fibonacci number, using Sum of the first $n$ Fibonacci numbers we get that $$ R [(N+n) F_n - F_{n+2} + 1]. $$ widgets have been produced up to time $F_n$.

share|cite|improve this answer

Your Answer


