Find Recurrence Relation for Flipping n Switches

[find_the_fun]

A circuit has n switches, all initially off. In order to be able to flip the ith switch, the (i-1)th switch must be on and all earlier switches off. The first switch can always be flipped. Find a recurrence relation for the total number of times the n switches must be flipped to get the nth switch on and all the others off.

I got \(\displaystyle f_n=f_{n-1}+2\) with initial condition \(\displaystyle f_1=1\) Is this right? This makes sense because to get the nth switch on, you need the (n-1)th switch on, and then you need to turn on the nth switch itself and turn off the (n-1)th switch. I have trouble explaining this using math though.

 

[Evgeny.Makarov]

Re: Finding a recurrence relation where (k-1)th switch must be on to turn on kth switch

I got \(\displaystyle f_n=f_{n-1}+2\) with initial condition \(\displaystyle f_1=1\) Is this right? This makes sense because to get the nth switch on, you need the (n-1)th switch on, and then you need to turn on the nth switch itself and turn off the (n-1)th switch.

You can't turn off the $(n-1)$th switch by flipping it alone.

 

[find_the_fun]

Re: Finding a recurrence relation where (k-1)th switch must be on to turn on kth switch

Speaking in general, what's the point of recurrence relations? Why not use a regular equation? Is it because in some situations it may be easier to derive/discover a recurrence relation?

 

[Evgeny.Makarov]

Re: Finding a recurrence relation where (k-1)th switch must be on to turn on kth switch

Is it because in some situations it may be easier to derive/discover a recurrence relation?

Yes. Recurrence relation is itself a function defined by recursion, i.e., the definition of such function refers to the function itself. And recurrence relation naturally accompany definitions by recursion, which may not even involve numbers (structural recursion). For example, it is easy to describe a recursive algorithm for solving Hanoi towers puzzle; a corresponding recurrence relation may count the required number of moves.

So, why is recursion useful?

(1) Recursive definitions are often simpler. For example, it is easy to come up with the recurrence relation for Fibonacci numbers from the description of the rabbit population growth, as in the original puzzle. Deriving Binet's formula is harder.

(2) Certain constructions of objects (numbers, lists, etc.) naturally lead to recursive definitions. Such constructions define how to build an object from existing ones: e.g., a list is either empty or a pair of a number and a list. Functions that take lists as arguments are often defined by recursion.

(3) The "divide-and-conquer" and dynamic programming techniques of building algorithms (e.g., binary search) use recursion to increase efficiency.

(4) Functions defined by recursion often can't be expressed using only operations from the definition. For example, the definition of factorial uses only 1 and multiplication, but the factorial is different from the four arithmetic operations. Concerning hailstone numbers, nobody knows if every starting number eventually turns into 1.

Remark: Some people make distinction between recurrence and recursion: the former is a special case of the latter. Since natural numbers can be considered built from 0 by using successor, a definition that gives f(n+1) from f(n) is a definition by recurrence, while the one that produces f(n) from f(n/2) uses more general recursion.

 

[blue_raver22]

Yes, your recurrence relation is correct. To explain it using math, we can use the fact that the total number of times the n switches must be flipped is equal to the number of times the (n-1)th switch must be flipped (to turn it on) plus 2 (to turn on the nth switch and turn off the (n-1)th switch). This can be written as f_n = f_{n-1} + 2. Additionally, the initial condition f_1 = 1 represents the fact that to turn on the first switch, no flips are needed as it is already on. Therefore, this initial condition satisfies the recurrence relation.