Mathematical Foundation of Computer Science

DHARM

36 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

For n = 5, c 5 = abkk 5

0

5

∑ − = a 0 b 5 + a 1 b 4 + a 2 b 3 + a 3 b 2 + a 4 b 1 + a 5 b 0 = 6

For n = 6, c 6 = abkk 6

0

6

∑ − = a^0 b^6 + a^1 b^5 + a^2 b^4 + a^3 b^3 + a^4 b^2 + a^5 b^1 + a^6 b^0 = 6

Similarly, we find c 7 , c 8 , ...... = 0

Therefore, c

n

n

n

n

n=

≤≤

≤≤

≤≤

≥

R

S

||

T

|

|

12

34

656

07

for 0
for 3
for
for
Example 2.18 Consider the numeric functions an = 2n, for all n and bn = 0, for 0 ≤ n ≤ 2 and 2n,
for n ≥ 3. Determine the convolution anbn.
Sol. Let cn = anbn. Since we have the values for an and bn for different values for n i.e.,
a 0 = 2, a 1 = 2, a 2 = 4, a 3 = 8, ........................
and b 0 = 0, b 1 = 0, b 2 = 0, b 3 = 2^3 , b 4 = 2^4 , .............
Hence, c 0 = a 0 b 0 = 2.0 = 0
c 1 = a 0 b 1 + a 1 b 0 = 2.0 + 1.0 = 0
c 2 = a 0 b 2 + a 1 b 1 + a 2 b 0 = 4.0 + 2.0 + 1.0 = 0
c 3 = a 0 b 3 + a 1 b 2 + a 2 b 1 + a 3 b 0 = 0 + 1.2^3 = 1.2^3
c 4 = a 0 b 4 + a 1 b 3 + a 2 b 2 + a 3 b 1 + a 4 b 0 = 2.2^3 + 1.2^4 = 2.2^4
c 5 = a 0 b 5 + a 1 b 4 + a 2 b 3 + a 3 b 2 + a 4 b 1 + a 5 b 0
= 4.2^3 + 2.2^4 + 1.2^5 + 3.2^5 = 3.2^5
Or, in general cn = (n – 2) 2n
Therefore, the convolution is given as,

c

n

n nnn

=

≤≤

−≥

R

S

T

002

22 3

for

()for

Example 2.19 Let an, bn and cn are the numeric functions, i.e., an*bn = cn, where

an=SR^10 ffor nor n 0≥= 2

T

and cn=RS^10 ffor nor n 0≥=

T^1

Determine bn.

Sol. Since we have cn = an*bn = abknk

k

n

−

=

∑

0

Therefore,

For n = 0, c 0 = a 0 .b 0 ⇒ 1 = 1.b 0 ⇒ b 0 = 1

For n = 1, c 1 = abkk 1

0

1

∑ − = a 0 b 1 + a 1 b 0 ⇒ 1. b 1 + 2. b 0 = 0. Using b 0 = 0, b 1 = (– 2)^1.

For n = 2, c 2 = abkk 2

0

2

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

⇒ 1. b 2 + 2. b 1 + 0. b 0 = 0. So b 2 = – 2 b 1 ⇒ b 2 = (– 2)^2.