Question
A row of $n$ light bulbs must be turned on. Initially they are all off. The first bulb can always be turned on or off. For $i> 1$, the $i$th bulb can be switched (turned on or off) only when $i-1$ is on and all other earlier bulbs are off. Let $a_n$ be the number of switches needed to turn all light bulbs on and let $b_n$ be the number of switches needed to turn on the $n$th bulb for the first time. Find recurrences for $a_n$ and $b_n$.
The above question is from Aigner's A course in Enumeration.
My Attempt
The initial conditions are $a_0=b_0=0$ and computing the first couple of values gives us for example $a_1=b_1=1$, $a_2=b_2=2$, and $a_3=5;\, b_3=4$.
We note that $a_n=b_n+a_{n-2}$ for $n\geq 2$. Indeed, to switch on all lights we must first switch on the $n$th light for the first time (and after doing so light $n-1$ and $n$ are on, all others off) and then switch on the reamining $n-2$ lights.
I was unable to come up with a recurrence for $b_n$.
My Problem
I looked in the back of the book and the following recurrence for $b_n$ is given $$ b_n=a_{n-1}+a_{n-2}+1\quad (n\geq 2)\tag{1} $$ How does one explain the recurrence above (combinatorially)? My idea is that to get to the state that light $n$ is on for the first time it must be the case that we get to the state when only $n-2$ and $n-1$ are on and then we turn off $n-2$ and turn on $n$. But I am unable to relate it to the number of switches to have an initial segment of lights on.
Any help is appreciated.
The sequence of moves to reach the state where bulb $n$ is on for the first time looks something like this: $$ 00000000\to \dots \to 00000010\to 00000011 $$ However, if we could show it furthermore looked something like this: $$ 00000000\;\;\underbrace{\to \dots\to}_{a_{n-1}}\;\; 11111110 \;\;\underbrace{\to \dots\to}_{a_{n-2}}\;\; 00000010\to 00000011 $$ then the recurrence would be proved. The reason the second block takes $a_{n-2}$ moves is because of the symmetry of the problem; turning on $n-2$ takes the same time as turning off that many.
So, we would be done if we could prove this lemma:
Proof: This can be proven by induction. Suppose that any toggling of light $k$ is preceded by a time where lights $1$ to $k-1$ are all on, for all $k<n$. Now, before a toggling of light $n$, we must reach state $$ 0000001*\tag{1} $$ which is preceded at some point in the past by $$ 0000011*\tag{2} $$ By induction, to move from $(2)$ to $(1)$, which involves a toggling of bulb $n-2$, there needs to a time where bulbs $1$ through $n-3$ are all on. But in $(2)$, we additionally have that bulbs $n-2$ and $n-1$ are on, so all of bulbs $1$ through $n-1$ are on, as desired.