How to prove a bitstring structural induction problem

Question

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.

Answer 1

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.