Understanding an example of proof by Induction

Question

The following example is taken from Kenneth Rosen's discrete mathematics book.

> EXAMPLE 13: Suppose that a_m,n is defined recursively for (m, n) ∈ N × N by a_0,0 and

$$ a_m,_n = \left\{ \begin{array}{ll} a_{m-1,n}\,+1 & \quad n=0\,and\,m>0 \\ a_{m,n-1} & \quad n>0 \end{array} \right. $$

Show that a_m,n=m+n(n+1)/2 for all (m,n) ∈ N×N,that is,for all pairs of nonnegative integers.

Solution:We can prove that a_m,n =m+n(n+1)/2 using a generalized version of mathematical induction. The basis step requires that we show that this formula is valid when (m, n) = (0, 0). The induction step requires that we show that if the formula holds for all pairs smaller than (m, n) in the lexicographic ordering of N × N, then it also holds for (m, n).

BASIS STEP: Let (m, n) = (0, 0). Then by the basis case of the recursive definition of a_m,n we have a_0,0 =0. Furthermore, when m=n=0, m+n(n+1)/2= 0+(0·1)/2=0. This completes the basis step.

INDUCTIVE STEP: Suppose that a_m',n' = m′ + n′(n′ + 1)/2 whenever (m′, n′) is less than (m, n) in the lexicographic ordering of N × N. By the recursive definition, if n = 0, then a_m,n = a_m-1,n + 1. Because (m − 1, n) is smaller than (m, n), the inductive hypothesis tells us that a_m-1,n =m−1+n(n+1)/2, so that am,n =m−1+n(n+1)/2+1= m + n(n + 1)/2, giving us the desired equality. Now suppose that n > 0, so a_m,n = a_m,n-1 + n. Because (m, n − 1) is smaller than (m, n), the inductive hypothesis tells us that a_m,n-1 = m+(n−1)n/2, so a_m,n =m+(n−1)n/2+n=m+(n −n+2n)/2=m+n(n+1)/2. This finishes the inductive step.

I have problem understanding the inductive step that how the both cases n = 0, a_m,n = a_m-1,n + 1 and n > 0, so a_m,n = a_m,n-1 + n. are equal to m+n(n+1)/2.

I have tried to solve these two cases algebraically but they are not making any sense to me I want to know what is the logic behind proving the in both cases of inductive steps we get m+n(n+1)/2

Answer 1

Long comment : please, take care of the correct reading of formulas…

The inductive step is :

assume that $a_{m',n'} = m' +\dfrac { n′(n′ + 1)} {2}$ whenever $(m′, n′) < (m, n)$ in the lexicographic ordering.

Now, we have to consider two cases :

(i) $n=0$ (obviously $m >0$, because otherwise we have agian the base case).

For $n=0$, by the recursive definition, we have that $a_{m,n} = a_{m-1,n}+1$.

Because $(m−1, n) < (m, n)$, the inductive hypothesis tells us that $a_{m-1,n}=(m-1) + \dfrac {n(n+1)}{2}$,

and thus $a_{m,n} = (m-1) + \dfrac {n(n+1)}{2}+1 = m + \dfrac {n(n + 1)}{2}$, giving us the desired equality.

(ii) $n >0$.