# How to prove a bitstring structural induction problem

A bitstring is a string consisting of only 0s and 1s. Define “·” to be the operation of concatenation, and let $$\epsilon$$ be the empty bitstring. Consider the following recursive definition of the function “count”, which counts the number of 1’s in the bitstring:
• count$$(\epsilon) = 0$$,
• count$$(s \cdot 1) = 1 +$$ count($$s$$),
• count$$(s \cdot 0) =$$ count($$s$$).
How would I use structural induction to prove that count$$(s \cdot t) =$$ count($$s$$)+count($$t$$)? I know that the base case is $$t = \epsilon$$, but have no idea what to do for the inductive step.

• I recommend using two base cases here: count$(s \cdot 0) =$ count$(s)$ and count$(s \cdot 1) = 1 +$ count$(s)$. Nov 10, 2022 at 12:45

Here we have given the set of bitstrings and a function count which counts the number of $$1$$'s in a string. The function count is recursively defined via base case and constructor case:

• base case: count$$(\epsilon) = 0$$

• constructor case: count$$(s \cdot a) = a +$$count($$s$$), where $$a\in\{0,1\}\qquad\qquad\qquad(1)$$

In order to show for two bitstrings $$s,t$$ the claim \begin{align*} \color{blue}{\mathrm{count}(s\cdot t)=\mathrm{count}(s)+\mathrm{count}(t)}\tag{2} \end{align*} we will use the base case as well as the constructor case.

Base step:

Let $$s$$ be a bitstring. As base step we consider $$t=\epsilon$$. We obtain \begin{align*} \color{blue}{\mathrm{count}(s\cdot \epsilon)}&=\mathrm{count}(s\cdot \epsilon)\\ &=\mathrm{count}(s)\\ &=\mathrm{count}(s)+0\\ &\,\,\color{blue}{=\mathrm{count}(s)+\mathrm{count}(\epsilon)} \end{align*} and the base step follows.

Induction step: Let $$s,t$$ be bitstrings with $$t=t^{\prime}\cdot a, a\in\{0,1\}$$. According to the induction hypothesis we assume \begin{align*} \mathrm{count}(s\cdot t^{\prime})=\mathrm{count}(s)+\mathrm{count}(t^{\prime})\tag{3} \end{align*}

We obtain \begin{align*} \mathrm{count}(s\cdot t)&=\mathrm{count}(s\cdot \left(t^{\prime}\cdot a\right))\tag{\to definition of t}\\ &=\mathrm{count}(\left(s\cdot t^{\prime}\right)\cdot a))\tag{\to concatenation rule}\\ &=\mathrm{count}\left(s\cdot t^{\prime}\right)+a\tag{\to (1)}\\ &=\left(\mathrm{count}\left(s\right)+\mathrm{count}\left(t^{\prime}\right)\right)+a\tag{\to (3)}\\ &=\mathrm{count}\left(s\right)+\left(\mathrm{count}\left(t^{\prime}\right)+a\right)\\ &=\mathrm{count}\left(s\right)+\mathrm{count}\left(t^{\prime}\cdot a\right)\tag{\to (1)}\\ &\,\,\color{blue}{=\mathrm{count}\left(s\right)+\mathrm{count}\left(t\right)}\tag{\to definition of t} \end{align*} and the claim (2) follows.