1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes I know about it $\endgroup$ – sachal Nov 8 '19 at 7:57
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you now it has started to make sense $\endgroup$ – sachal Nov 8 '19 at 8:17
  • $\begingroup$ @sachal - you are welcome :-) $\endgroup$ – Mauro ALLEGRANZA Nov 8 '19 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.