Demostrar la desigualdad por inducción: $0 \leq h(n) \leq n$ para todos $n \in \mathbb{N_0}$

Question

$h: \mathbb{N_0} \rightarrow \mathbb{N_0}$ se define como:

$h(0) = 0 \\ \forall k \in \mathbb{N_+}: h(2k) = h(k) \\ \forall k \in \mathbb{N_0}: h(2k+1) = 1+ h(k)$

a) Cree una tabla con $n$ y $h(n)$ para cada $n \in \mathbb{N_0}, n \leq 7$

b) Demuestre por inducción que $0 \leq h(n) \leq n$ para todos $n \in \mathbb{N_0}$

Sugerencia: Utiliza la inducción fuerte.

c) ¿Qué conexión hay entre $w \in \{0,1\}^*$ y $h(Num_2(w))$

a)

• $n=0: h(n) = 0$
• $n=1: h(n) = 1$
• $n=2: h(n) = 1$
• $n=3: h(n) = 2$
• $n=4: h(n) = 1$
• $n=5: h(n) = 2$
• $n=6: h(n) = 2$
• $n=7: h(n) = 3$

b) Caso base: $n=0: h(0) = 0 \Rightarrow 0 \leq h(0) \leq 0$

Hipótesis inductiva:

$0 \leq h(n) \leq n$ se cumple para algunos $n \in \mathbb{N_0}$

Paso inductivo:

$n \rightarrow n+1$ para mostrar: $$$0 \leq h(n+1) \leq n+1$

1.caso: $n$ es par, $n=2k$

$h(n+1) = h(2k +1)$ = 1+ h(k)

2.caso: $n$ es impar, $n=2k +1$

$h(n+1) = h(2k +2) = h(2 \cdot (k+1)) = h(k+1)$

Así, en el primer caso, cuando $n$ es par, pasará por todos los impar $n$ .

En el segundo caso, cuando $n$ es impar, pasará por el incluso $n$ .

Esta era la única idea que tenía pero parece que no me lleva a la dirección correcta.

¿Cómo puedo llegar a una desigualdad con $n + 1$ ?

Answer 1

En dmtri comentó la pregunta,

para fuerte inducción la hipótesis inductiva sería que $0\le h(k)\le k$ para todos $k\le n$ .

Con eso, no es difícil demostrar que $0\le h(n+1)\le n+1$ y completar la prueba,

utilizando los dos casos que has considerado.

Caso 1. $n=2k.$

Entonces $h(n+1)=h(k)+1,$ y, por la hipótesis inductiva, $0\le h(k)+1\le k+1<n+1$ .

Caso 2. $n=2k+1.$

Entonces $h(n+1)=h(k+1)$ y, utilizando de nuevo la hipótesis inductiva,

$0\le h(k+1)\le k+1<n+1$ .