Generando una pregunta de relación de recurrencia.

Question

Un juego de cambio tiene$n$ interruptores, todos inicialmente en la posición OFF. Para poder activar el interruptor$ith$, el interruptor$(i-1)st$ debe estar ENCENDIDO, y todos los interruptores anteriores deben estar APAGADOS. El primer interruptor siempre puede ser volteado. Encuentre una relación de recurrencia y una condición inicial para$f_n$, el número total de veces que los interruptores$n$ deben ser girados para que el interruptor$nth$ esté ENCENDIDO y todos los demás APAGADOS.

Answer 1

La relación de recurrencia es$f_n=n+\sum_{i=0}^{n-1}f_i$ para$n\geq0$. La condición inicial es$f_0=0$.

Para ver este resultado, considere el requisito de que el interruptor$nth$ esté activado, que es el interruptor$(n-1)th$ que esté activado y el resto esté desactivado. Hasta ahora, tenemos$f_{n-1}+1$ movimientos. Para que$(n-1)th$ cambie a estar encendido, necesitamos$(n-2)th$ para estar encendido y el resto para estar apagado. Esto acumula otros$f_{n-2}+1$ movimientos. Continuando con este patrón hasta el primer interruptor, tenemos$(1+f_{n-1})+(1+f_{n-2})+\cdots+(1+f_1)+(1+f_0)=n+\sum_{i=0}^{n-1}f_i$. Verificando manualmente los primeros términos,$f_0=0,f_1=1,f_2=3,f_3=7$.

Answer 2

Pista: ¿Qué has intentado? ¿Hay un buen candidato para el$n$ que es la condición inicial útil? Para la recurrencia, parece más útil pensar en el nuevo cambio (que va de$n-1$ a$n$) como el primero, no el último.