Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 37

For n = 3, c 3 = abkk 3

0

3

∑ − = a 0 b 3 + a 1 b 2 + a 2 b 1 + a 3 b 0

⇒ 1. b 3 + 2. b 2 + 0. b 1 + 0 = 0. So b 3 = – 2b 2 = (– 2)^3.
In general, we obtain bn = (– 2)n for n ≥ 0.
Example 2.20 Let an, bn and cn are the numeric functions, where

a

1forn0

3forn1

2 for 2 n 5

0forn6

n=

=

=

≤≤

≥

R

S

||

T

|

|

, bn =

0for0n10

1 for n 11

≤≤

≥

R

S

T

and c

2 for 0 n 9

n= 3 for n 10

≤≤

≥

R

S

T

Determine cn* (an*bn).

Sol. Let an*bn = c′n = abknk
k

n

−

=

∑

0

Since,

• bn = 0 for 0 ≤ n ≤ 10, therefore c′n = 0 for 0 ≤ n ≤ 10, and


• bn = 1 for n ≥ 11, therefore
  c′n = abkk
  k

11

0

11

−

=

∑ = a 0 b 11 + 0 = 1.1 = 1

So we have c

n

′=n n

≤≤

≥

R

S

T

010

11

for 0 and

1for

,

and given c n

n n

= ≤≤

≥

R

S

T

29

10

for 0 and

3for

,

Now we find the convolution of cn with c′n and let, cn * (c′n) = dn i.e.,

dn = cn*c′n = ccknk

k

n

′ −

=

∑

0

• For 0 ≤ n ≤ 10, dn = 0 [∴ c′n = 0 for 0 ≤ n ≤ 10]


• For n ≥ 11, dn can be determine as follows,

d 11 = ∑cckk′ 11 −

0

11

= c 0 c′ 11 + 0 = 1.2

d 12 = ∑cckk′ 12 −

0

12

= c 0 c′ 12 + c 1 c′ 11 + 0 = 2.1 + 2.1 = 2.2

d 11 = ∑cckk′ 13 −

0

13

= c 0 c′ 13 + c 1 c′ 12 + c 2 c′ 11 + 0 = 3.2

Similarly we can determine d 20 upto n = 20, i.e. d 20 = 10.2
And for n = 21,

d 21 = ∑cckk′ 21 −

0

21

= (c 0 + c 1 + ..... + c 9 ) + c 10

[∴ c′ 21 to c′ 11 = 1 and rest are 0]

= (10.2) + 1.3