Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

Question

So I'm trying to solve this week's FiveThirtyEight Riddler.

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.

What is the expected number of lit buttons when the elevator begins its ascent?

I think I'm close, but I'm having trouble solving the following recurrence relation. I got the following equation to find the expected number of lit buttons in a given building of M floors and N people.

f_n = 1 + f_n-1*(1- 1/M)

f_n is the expected number of lit up buttons for a given N & M. M is some constant, so the quantity (1- 1/M) is essentially a constant. I was hoping someone could point me in the right direction to solve such a series.

Additionally, I simulated the problem in R, and the formula above seemed to match the simulation. However, if you see something wrong, please let me know.

I also thought that my equation right now include the top floor elevator light, but in the puzzle that light actually won't be pressed. So could I just subtract that constant 1 from my equation, making the formula a simple geometric series?

Answer 1

We first convert from non-homogeneous to homogeneous: $$ f_n = c f_{n-1} + 1 $$ with $c = 1 - 1/M$. This means $$ f_{n-1} = c f_{n-2} + 1 $$ and for the difference $$ f_n - f_{n-1} = c (f_{n-1}- f_{n-2}) \iff \\ f_n = (c +1) f_{n-1} - c f_{n-2} $$ and for this we can use the usual algorithm: The characteristic polynomial is $$ p(t) = t^2 - (c+1) t + c $$ with roots $r_1$, $r_2$: $$ 0 = (t - (c+1)/2))^2 + c - (c+1)^2/4 \iff \\ \frac{c^2 - 2c + 1}{4} = \left( t - \frac{c+1}{2} \right)^2 \iff \\ t = \frac{c+1 \pm \sqrt{c^2-2c + 1}}{2} $$ and solution $$ f_n = k_1 r_1^n + k_2 r_2^n $$ The constants $k_1$, $k_2$ have to be determined from initial conditions, e.g.: $$ f_1 = k_1 r_1 + k_2 r_2 \\ f_2 = k_1 r_1^2 + k_2 r_2^2 $$

Answer 2

If one person gets in one button will be lit however many floors (though you may as well assume $M\ge 2$) $f_1=1$

Put $K=1-\frac{1}{M}$, then: $$ \begin{aligned} f_1&=1\\ f_2&=1+K\\ f_3&=1+K(1+K)=1+K+K^2\\ \vdots\\ f_n&=\sum_{k=0}^{n-1}K^k=\frac{K^n-1}{K-1} \end{aligned} $$