Answer to Question #256699 in Discrete Mathematics for Alina

Question

For the following recursive functions, Prove that a_m,n = m · n. Here a_m,n is defined recursively for (m, n) ∈ N × N.

a_m.n = { 0 if m=0

n+a_m-1,n if m!=0

Answer 1

For $m=0$ formula is obviously fulfilled. Check it for $m>0$ :

$a_{m,n}=n+a_{m-1,n}=(n+n)+a_{m-2,n}=\ldots=n\cdot m+ a_{0,n}=n\cdot m$