Question

Use generalized induction as was done in Example 13 to show that if ${\mathbf{a}}_{\mathbf{m}\mathbf{,}\mathbf{n}}$is defined recursively by ${\mathbf{a}}_{\mathbf{0}\mathbf{,}\mathbf{0}}\mathbf{=}\mathbf{0}$and ${\mathbf{a}}_{\mathbf{m}\mathbf{,}\mathbf{n}}\mathbf{=}\{\begin{array}{l}{a}_{m-1,n}+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}n=0\text{and}m>0\\ a_{m,n-1}+1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}n>0,\end{array}$

then${\mathbf{a}}_{\mathbf{m}\mathbf{,}\mathbf{n}}\mathbf{=}\mathbf{m}\mathbf{+}\mathbf{n}\mathbf{\text{for all}}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\in }\mathbf{N}\mathbf{\times }\mathbf{N}\mathbf{\text{.}}$

Short answer

It has been proved.

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: Basis step

This is true because

$\begin{array}{r}{\mathrm{a}}_{0,0}=0\\ \text{And}\\ \begin{array}{rl}{\mathrm{a}}_{0,0}& =0+0\\ & =0\end{array}\end{array}$

Inductive step

Assume that $a_{m,n}=m\text{'}+n$whenever

$\left(m\text{'},n\text{'}\right)<\left(m,n\right)$

If n = 0 then,

$\begin{array}{r}{a}_{m,n}=a_{m-1,n}+1\\ =m-1+n+1\\ =m+n-1+1\\ =m+n\end{array}$

If n > 0 then,

$\begin{array}{r}{a}_{m,n}=a_{m,n-1}+1\\ =m+n-1+1\\ =m+n+0\\ =m+n\end{array}$

Hence, proved