Considere la siguiente recurrencia:
f(1) = 1; f(2n) = 2f(n) -1, for n≥1; f(2n+1) = 2f(n) +1, for n≥1;
Entonces, ¿cuál de las siguientes afirmaciones es/son VERDADERAS?
(A)
f( 2n – 1) = 2n – 1
(B)
f( 2n ) = 1
(C)
f(5. 2 n ) = 2 n+1 +1
(D)
f(2 norte +1) = 2 norte +1
Respuesta: (A) (B) (C)
Explicación:
Opción A:
Opción B:
f(2n) = f(2.2n-1)
= 2f(2.2n-2) - 1)
= 2[2f(2n-2) - 1)]- 1
= 22 f(2n-2) - 2 -1
.....
= 2k f(2n-k) -[2k-1]
[∴ 2n-k = 1 ⇒ 2k = 2n]
= 2n-[2n -1] = 1
Opción C:
f(5.2n) = 2n+1+ 1
f(2n + 1) = 2f(n) + 1
// 2n+1 is always odd
Opción D:
f(2n+ 1) = f(2.2n-1+ 1)
= 2f(2n- 1) + 1
= 2f(2.2n-2) + 1
= 2[2f(2n-2) +1 ] + 1
= 22 f(2n-2) + 2 +1
.....
= 22 f(2n+k) +(2k-1)
[∴ 2n=2k]
= 2n+2n -1 = 2n+1- 1
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA