Question

(a) Give a recursive definition of the function m(S) , which equals the smallest digit in a nonempty string of decimal digits.

(b) Use structural induction to prove that $\mathbf{m}\mathbf{\left(}\mathbf{st}\mathbf{\right)}\mathbf{=}\mathbf{min}\mathbf{\left(}\mathbf{m}\mathbf{\right(}\mathbf{s}\mathbf{)}\mathbf{,}\mathbf{m}\mathbf{(}\mathbf{t}\mathbf{\left)}\mathbf{\right)}$.

Short answer

$\begin{array}{r}\left(\mathrm{a}\right)\mathrm{m}\left(\mathrm{ds}\right)=min(\mathrm{d},\mathrm{m}(\mathrm{s}\left)\right)\text{whenever}\mathrm{d}\in \{0,1,2,3,4,5,6,7,8,9\}\text{and}\mathrm{s}\in \mathrm{S}\\ \left(\mathrm{b}\right)\mathrm{m}\left(\mathrm{St}\right)=min\left(\mathrm{m}\right(\mathrm{s}),\mathrm{m}(\mathrm{t}\left)\right)\end{array}$

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.

Step 2: To give a recursive definition of the function  (a)

Assume that in a nonempty string of decimal digits, represent the smallest digit.

Let the set of nonempty strings of decimal digits be S.

Recursive step:

Now, let represent the string with the digit d added to the front of the string ds.

Then, the minimum of the digit d is the smallest digit in the spring $\mathrm{m}\left(\mathrm{ds}\right)=min(\mathrm{d},\mathrm{m}(\mathrm{s}\left)\right)\text{whenever}\mathrm{d}\in \{0,1,2,3,4,5,6,7,8,9\}\text{and}\mathrm{s}\in \mathrm{S}$

Step 3: To prove m(st)=min(m(s),m(t)) by structural induction.(b)

To prove: $m\left(st\right)=min\left(m\right(s),m(t\left)\right)$

Proof:

$\mathrm{m}\left(\mathrm{dS}\right)=min(\mathrm{d},\mathrm{m}(\mathrm{s}\left)\right)=min\left(\mathrm{m}\right(\mathrm{d}),\mathrm{m}(\mathrm{s}\left)\right)$

Thus, $m\left(st\right)=min\left(m\right(s),m(t\left)\right)$is proved by the principle of structural induction.