1
$\begingroup$

Prove that for every n ∈ N with n ≥ 1 exists a one step binary code Cn for the number interval [0..2 n −1] with code words of length n.

I have the hint of complete induction.

So my start would be that for n = 1 it exists

This would be

0

1

Now for n+1

I dont't know how to display this now? I had 2 code words for 1 For n+1 is should be 2^(n+1) ?

$\endgroup$
3
  • 1
    $\begingroup$ Yes, there are $2^{n+1}$ code words of length $n+1$. But make sure to use your inductive hypothesis that the claim is true for $n$. That is: you need to show that if you have gray codes for all words of length $n$, you can use that to create Gray codes for al words of length $n+1$ $\endgroup$
    – Bram28
    Commented Apr 17, 2020 at 19:13
  • $\begingroup$ How could I accomplish this? I have used n=1 ? Just claiming this in a hypothesis? And use this in the induction step? $\endgroup$
    – Rapiz
    Commented Apr 17, 2020 at 19:16
  • 1
    $\begingroup$ The $n=1$ case does not really come into play for the inductive step. That is,you don;t go from $1$ to $2$, because even if you show that, you then have to show that you can go from $2$ to $3$, etc. So, what you want to show is that in general, you can go from $n$ to $n+1$. And yes, for that, you can just claim as the inductive hypothesis that you have Gray codes for all words of length $n$. $\endgroup$
    – Bram28
    Commented Apr 17, 2020 at 19:19

1 Answer 1

1
$\begingroup$

Say you have a Gray sequence for words with length $n$: $a_1,\dots,a_{2^n}$. From this you can construct a Gray sequence at length $n+1$ as $$0a_1,0a_2,\dots,0a_{2^n},1a_{2^n},\dots,1a_2,1a_1$$ This accomplishes the inductive step – strong (complete) induction is not needed.

This operation of flipping the sequence and adding $0$s and $1$s to each side is why the Gray code is sometimes called the reflected binary code.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .