Question

(a) Give a recursive definition of the function ones (s) , which counts the number of ones in a bit string s.

(b) Use structural induction to prove that ones (st) = ones (s) + ones (t) .

Short answer

$$\begin{gathered} \left(\mathrm{a}\right)\mathrm{ones}\left(1\mathrm{s}\right)=\mathrm{ones}\left(\mathrm{s}\right)+1\mathrm{whenever}\mathrm{s}\in \mathrm{S} \\ \mathrm{ones}\left(0\mathrm{s}\right)=\mathrm{ones}\left(\mathrm{s}\right)\mathrm{whenever}\mathrm{s}\in \mathrm{S} \\ \left(\mathrm{b}\right)\mathrm{ones}\left(\mathrm{st}\right)=\mathrm{ones}\left(\mathrm{s}\right)+1\mathrm{ones}\left(\mathrm{t}\right) \end{gathered}$$

Step-by-step solution

The recursive definition of the sequence:

The recursive sequence is a sequence of numbers indexed by an integer and generated by solving a recurrence equation.

(a) To give a recursive definition of the function  

ones (s) represent the number of ones in a bit string and let S be the set of all bit strings.

Recursive step:Let represent the string with the bit 1 added to the front of the string , while represents the string with the bit 0 added to the front of the string .

$$\begin{gathered} \mathrm{ones}\left(1\mathrm{s}\right)=\mathrm{ones}\left(\mathrm{s}\right)+1\mathrm{whenever}\mathrm{s}\in \mathrm{S} \\ \mathrm{ones}\left(0\mathrm{s}\right)=\mathrm{ones}\left(\mathrm{s}\right)\mathrm{whenever}\mathrm{s}\in \mathrm{S} \end{gathered}$$

(b) To prove ones(st)=ones(s)+ones(t) by structural induction.

To prove: $\mathrm{ones}\left(\mathrm{st}\right)=\mathrm{ones}\left(\mathrm{s}\right)+\mathrm{ones}\left(\mathrm{t}\right)$

Proof: $\begin{array}{r}\text{ones}\left(1\mathrm{s}\right)=\text{ones}\left(\mathrm{s}\right)+1=1+\text{ones}\left(\mathrm{s}\right)=\text{ones}\left(1\right)+\text{ones}\left(\mathrm{s}\right)\\ \mathrm{ones}\left(0\mathrm{s}\right)=\mathrm{ones}\left(\mathrm{s}\right)=0+\text{ones}\left(\mathrm{s}\right)=\text{ones}\left(0\right)+\mathrm{ones}\left(\mathrm{s}\right)\end{array}$

Thus,$\mathrm{ones}\left(\mathrm{st}\right)=\mathrm{ones}\left(\mathrm{s}\right)+\mathrm{ones}\left(\mathrm{t}\right)$ by the principle of structural induction.