Generating a recurrence relation question

Question

A switching game has $n$ switches, all initially in the OFF position. In order to be able to flip the $ith$ switch, the $(i-1)st$ switch must be ON, and all earlier switches OFF. The first switch can always be flipped. Find a recurrence relation and initial condition for $f_n$ , the total number of times the $n$ switches must be flipped to get the $nth$ switch ON and all others OFF.

Answer 1

Hint: What have you tried? Is there a good candidate for the $n$ that is the useful initial condition? For the recurrence, it seems more useful to think about the new switch (going from $n-1$ to $n$) as the first one, not the last.

Answer 2

The recurrence relation is $f_n=n+\sum_{i=0}^{n-1}f_i$ for $n\geq0$. The initial condition is $f_0=0$.

To see this result, consider the requirement for the $nth$ switch to be on, which is $(n-1)th$ switch to be on and the rest to be off. So far, we have $f_{n-1}+1$ moves. For $(n-1)th$ switch to be on, we need $(n-2)th$ to be on and the rest to be off. This accumulates another $f_{n-2}+1$ moves. Continuing this pattern all the way to the first switch, we have $(1+f_{n-1})+(1+f_{n-2})+\cdots+(1+f_1)+(1+f_0)=n+\sum_{i=0}^{n-1}f_i$. Manually checking the first few terms, $f_0=0,f_1=1,f_2=3,f_3=7$.