fill-in-the-blank induction proof

Question

I'm stuck at homework task I'm working on. I would really appreciate some help.

Here is the task:

Let $f$ be a function on binary numbers defined recursively as follows.

1. $f(0) = 1$ and $f(1) = 0$
2. $f(b0) = f(b)1$ , where $b$ is a binary number
3. $f(b1) = f(b)0$, where $b$ is a binary number

The following is a proof by induction that $f(f(b)) = b$ for all binary numbers $b$. Find out what should be in the empty boxes below.

Basic-step. It is the $1_____$ which holds for $b = 0$ and $b = 1$ By inserting $0$ for $b$, we get $f(f(0)) = 0$ The following calculation shows that this is true.

• $f(f(0)) = f(1)$ at point $1$ in the definition of $f$,

• $= 0$ at point $1$ in the definition of $f$

By inserting $1$ for $b$, we get $f(f(1)) = 1$. The following calculation shows that this is true.

• $f (f (1)) = f (0)$ at point $1$ in the definition of $f$

• = $1$ at point $1$ in the definition of $f$

$2_____$*step*. Assume that the statement holds for a binary number $b$, that is, $f(f(b)) = b$ which is $3_____$, and from this, we must show that the $4_____$ holds for a binary number $bx$, that is $f(f(bx))$ = $5_____$, where $x$ is either $0$ or $1$ We have two cases, one for $x = 0$ and one for $x = 1$

If $x = 0$ we get the following.

• $f(f(b0)) = f(f(b)1)$ at $6_____$ in the definition of $f$
• $= f(f(b))0$ at point $3$ in the definition of $f$
• $= b0$ by induction hypothesis

If $x = 1$, we get the following-

• $f(f(b1)) =$ $f$($7_____$) at $8_____$ in the definition of $f$
• $= f(f(b))1$ at point $2$ in the definition of $f$
• $= b1$ by induction hypothesis

At $9_____$ it follows that $10_____$ for all binary numbers $b$.

Edit:

I tried solving this task, would appreciate if someone could check if I've done this correctly:

1. $f(f(b))$

2. Induction-step

3. $f(b)$

4. $f(f(bx))$

5. $bx$

6. point $2$

7. $f(f(b)0)$

8. point $3$

9. induction

10. assumption is true

Thanks a lot.

Answer 1

1. O.K.
2. O.K. (technically, just induction, because you already have step).
3. I don't think so, but I'm not sure what your book wants from its clairvoyant readers. Maybe the statement we need to prove?
4. I think they want assumption, because $f(f(b))$ by itself means nothing.
5. O.K.
6. O.K.
7. O.K.
8. O.K.
9. Might be induction step.
10. O.K.

I will quote dfeuer, because it is pity that this remains only in the comments:

I suggest you place your textbook in the recycling bin for appropriate disposal.

Answer 2

I am not clear what they mean by "$f(b0) = f(b)1$" and "$f(b1) = f(b)0 $". Do they mean $f(2b) = 2f(b)+1$ and $f(2b+1) = 2f(b)$? This could be written as $f(n) = f(\lfloor n/2 \rfloor) +1 - (n \mod 2) $

This does not agree with your question (unless I misunderstand) because of this:

Let's compute the first few $f(n)$. Since $f(0) = 1$ and $f(1) = 0$, $f(2) = 2f(1)+1=1$, $f(3) = 2f(1) = 0$, $f(4) = 2f(2)+1 = 3$, $f(5) = 2f(2) = 2$, $f(6) = 2f(3)+1 = 1$, $f(7) = 2f(3) = 0$.

By induction, $f(2^k-1) =2f(2^{k-1}-1) =0$. Also, $f(2^k) =2f(2^{k-1})+1 =2^k-1 $.

Also by induction, if $n \ge 1$ then $f(n) \le n-1$. Proof: True for $n=1$. If $n \ge 1$, $f(2n) = 2f(n)+1 \le 2(n-1)+1 = 2n-1$ and $f(2n+1) =2f(n) \le 2(n-1) =2n-2 \le 2n $.

Looking at these, $f(f(7)) =f(0) = 1 \ne 7 $.

Staring at these, I might conjecture that $f(b)$ is the one's complement of $b$ in binary up to the highest $1$ digit in $b$.

That's all, folks.