Question

Use Exercise 37 and mathematical induction to show that $\mathrm{I}\left({\mathbf{w}}^{\mathrm{i}}\right)=\mathbf{i}.\mathrm{I}\left(\mathbf{w}\right)$, where is a string and is a nonnegative integer.

Short answer

The given statement is true.

Step-by-step solution

Introduction

Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. Step 1(Base step) − It proves that a statement is true for the initial value.

 Step 2: Solution

Let be the statement that $t\left(w^i\right)=i.l\left(w\right)$

Basis step:

p (0) is true because$\begin{array}{r}ı\left(w^0\right)=0.l\left(w\right)\\ =0\end{array}$

Inductive step:

Assume that p (k) is true.

i.e. $t\left(W^k\right)=k\cdot l\left(W\right)$

We have to prove that p (k + 1) is true.

Now

$\begin{array}{r}t\left(W^{k+1}\right)=t\left(W\cdot W^k\right)\\ =i\left(W\right)+t\left(W^k\right)\\ =i\left(W\right)+k\cdot l\left(W\right)\\ =i\left(W\right)(1+k)\\ =(1+k)\cdot t\left(w\right)\end{array}$

Therefore p (k + 1) is true,

Hence from the principle of mathematical induction the given statement is true.