# Understanding an example of proof by Induction

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

> EXAMPLE 13: Suppose that am,n is defined recursively for (m, n) ∈ N × N by a0,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 am,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 am,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 am,n we have a0,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 am',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 am,n = am-1,n + 1. Because (m − 1, n) is smaller than (m, n), the inductive hypothesis tells us that am-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 am,n = am,n-1 + n. Because (m, n − 1) is smaller than (m, n), the inductive hypothesis tells us that am,n-1 = m+(n−1)n/2, so am,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, am,n = am-1,n + 1 and n > 0, so am,n = am,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

• Yes I know about it – sachal Nov 8 '19 at 7:57

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$$.

• Thank you now it has started to make sense – sachal Nov 8 '19 at 8:17
• @sachal - you are welcome :-) – Mauro ALLEGRANZA Nov 8 '19 at 8:21