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.
 A: 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.

