cuelgo la prueba por inducción que comentara. a mi juicio no es complicada.
voy a probar \( (\forall m: (\forall n : n<m : P(n)) : P(m)) \),
donde la propiedad \( P \) es
\( P(n) := b_n = n-1 \)
* cuando \( m = 1 \), debo probar \( P(1) \), o sea \( b_1 = 1-1 \), lo que es inmediato por la definición de \( b \)
* cuando \( m > 1 \) y es par, puedo escribir \( m = 2n \); debo probar \( P(2n) \), o sea \( b_{2n} = 2n-1 \). Esto se desprende de lo siguiente:
\(
\begin{array}{lr}
b_{2n} \\
= 2 b_n + 1 & \mbox{(uso HI)}\\
= 2 (n-1) + 1 \\
= 2n - 1.
\end{array}
\)
* cuando \( m > 1 \) y es impar, puedo escribir \( m = 2n+1 \); debo probar \( P(2n+1) \), o sea \( b_{2n+1} = 2n \). Esto se desprende de lo siguiente:
\(
\begin{array}{lr}
b_{2n+1} \\
= b_n + b_{n+1} + 1 & \mbox{(uso HI)}\\
= (n-1) + (n+1-1) + 1 \\
= 2n.
\end{array}
\)
saludos