$h: \mathbb{N_0} \rightarrow \mathbb{N_0}$ is defined as:
$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) Create a table with $n$ and $h(n)$ for every $n \in \mathbb{N_0}, n \leq 7$
b) Prove by induction that $0 \leq h(n) \leq n$ for all $n \in \mathbb{N_0}$
Hint: Use strong induction.
c) Which connection is between $w \in \{0,1\}^*$ and $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) Base case: $n=0: h(0) = 0 \Rightarrow 0 \leq h(0) \leq 0$
Inductive hypothesis:
$0 \leq h(n) \leq n$ holds true for some $n \in \mathbb{N_0}$
Inductive step:
$n \rightarrow n+1$, to show: $$$0 \leq h(n+1) \leq n+1$
1.case: $n$ is even, $n=2k$
$h(n+1) = h(2k +1)$ = 1+ h(k)
2.case: $n$ is odd, $n=2k +1$
$h(n+1) = h(2k +2) = h(2 \cdot (k+1)) = h(k+1)$
So in the first case when $n$ is even, it will go through all of the odd $n$.
In the second case when $n$ is odd, it will go through the even $n$.
This was the only idea I had but it doesn't seem to get me to the right direction.
How do I get to an inequality with $n + 1$?
As dmtri commented on the question,
for strong induction, the inductive hypothesis would be that $0\le h(k)\le k$ for all $k\le n$.
With that, it is not difficult to show that $0\le h(n+1)\le n+1$ and complete the proof,
using the two cases you considered.
Case 1. $n=2k.$
Then $h(n+1)=h(k)+1,$ and, by the inductive hypothesis, $0\le h(k)+1\le k+1<n+1$.
Case 2. $n=2k+1.$
Then $h(n+1)=h(k+1)$, and, again using the inductive hypothesis,
$0\le h(k+1)\le k+1<n+1$.