Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 29

Example 2.6. Let an be a numeric function such that an is equal to the reminder when integer

is divided by 17. Assume b be other numeric function such that bn is equal to 0 if integer n is

divisible by 3, and equal to 1 otherwise.

(i)Let cn = an + bn , then for what values of n, cn = 0 and cn = 1.

(ii)Let dn = an * bn , then for what values of n, dn = 0 and dn = 1.

Sol. Construct the numeric functions for a and b,

Here, an =

0 0 17 34 17

11835 171

21936 172

16 33 50 17 16

for

for

for

...

...

for

nk

nk

nk

nk

==

==+

==+

==+

R

S

|

|

T

|

|

, , , ......

, , ......

, , ......

.. ... ...... ...

.. ... ...... ...

, , ......

(for k = 0, 1, 2, .....)

and bn = RS 100363 otherwisefornk==
T

, , ,......

(i) Since cn = an + bn, then cn = 0 only when both an and bn equal to zero, at n = 0.

To determine other coincident points we observe that when an is also divisible by 3, cn = 0,

i.e., n = 17 k * 3 = 51 k (for k = 0, 1, 2, ......)

Therefore, for n = 0, 51, 102, .......; cn = 0.

Likewise cn = 1, if an = 0 and bn = 1, or an = 1 and bn = 0.

an = 0 for n = 17 k and bn = 1 for n is not a multiple of 3. Therefore, cn = 1 when n is

divisible by 17 and not a multiple of 3.

Otherwise, an = 1 for n = 17k + 1 and bn = 0 for n is a multiple of 3. Therefore, cn = 1 when

n = 17k + 1 and multiple of 3.

(ii) Since, dn = an ∗ bn, and dn = 0 on following conditions,

• an = 0 and bn = 0, when n = 51 k


• an = 0 and bn ≠ 0, when n = 17 k and not a multiple of 3


• an ≠ 0 and bn = 0, when n is not a multiple of 17 and 3
  2.2.3 Multiplication with a scalar factor to numeric function returns a numeric function.
  For example, let an be a numeric function and m be any scalar (real number), then m.an
  will be a numeric function whose value at n is equal to m times an.
  For example, if numeric function an = 2n + 3 for n ≥ 0, then 5.an = 5.(2n + 3) or 5.2n + 15
  for n ≥ 0 is a numeric function.
  2.2.4 Let an and bn are two numeric functions then the quotient of an and bn is denoted by
  an/bn is also a numeric function, and its value at n is equal to the quotient of an/bn.
  2.2.5 Let an be a numeric function then modulus of an is denoted by |an|, and defined as,

|an| =

R−<

S

T

an

a

n

n

if

otherwise

0

For example, let an = (– 1)n (3/n^2 ) for n ≥ 0, then
|an| = (3/n^2 ) for n ≥ 0
2.2.6 Let an be a numeric function and I is any integer positive, then SI an is a numeric
function and defined as,

SI an =

00 1

1

for I

for I

≤≤−

≥

R

S

T −

n

ann