Answer to Question #148278 in Discrete Mathematics for Promise Omiponle

Question

Define a function fm: N x N ->N as follows: fm(n, k) =k if 0 ≤ n < m, and fm(n, k) =fm(n-m, k+1) otherwise. Describe in terms of a single well-known arithmetic operation what fm(n, 0) is computing.

Answer 1

If 0 ≤ n < m, then f_m(n,0) = 0

Suppose m ≤ n < 2m

f_m(n, 0) = f_m(n-m, 0+1)

Now m – m ≤ n - m < 2m – m

=> 0 ≤ n – m < m

=> f_m(n – m, 0 + 1) – 0 + 1 = 1

=> f_m(n, 0) = 1 for m ≤ n < 2m

Suppose 2m ≤ n < 3m

f_m(n,0) = f_m(n – m, 0 + 1)

Now 2m – m ≤ n – m < 3m – m

=> m ≤ n – m < 2m

=> f_m(n – 2m, 2) = 2

=> f_m(n – m, 0 + 1) = 2

=> f_m(n, 0) = 2 for 2m ≤ n < 3m

And so on

In other words, f_m(n, 0) is computing the quotient of n ÷ m