Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 35

Sol. Using the convolution formula,

cn = an*bn = abknk

k

n

−

=

∑

0

= a 0 bn + a 1 bn–1 + ........ + an–1 b 1 + an b 0

Since we have,
a 0 = a 1 = a 2 = 1 and a 3 = a 4 = ...... = 0
and b 0 = b 1 = b 2 = 1 and b 3 = b 4 = ...... = 0
Hence, c 0 = a 0 b 0 = 1.1 = 1
c 1 = a 0 b 1 + a 1 b 0 = 1.1 + 1.1 = 2
c 2 = a 0 b 2 + a 1 b 1 + a 2 b 0 = 1.1 + 1.1 + 1.1 = 3
c 3 = a 0 b 3 + a 1 b 2 + a 2 b 1 + a 3 b 0 = 0.0 + 1.1 + 1.1 + 0.1 = 2
c 4 = a 0 b 4 + a 1 b 3 + a 2 b 2 + a 3 b 1 + a 4 b 0 = 1.0 + 1.0 + 1.1 + 0.1 + 0.1 = 1
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
= 1.0 + 1.0 + 1.0 + 0.1 + 0.1 + 0.1 = 0
Similarly we find that rests of the values of c for n > 5 are all zero.
Therefore, convolution is given as,

c

n

n

n

n

n

n=

=

=

=

=

=

R

S

|

||

T

|

|

|

10

21

32

23

14

0

for

for

for

for

for

otherwise

Example 2.17 Let an = 1 for n ≥ 0 and

b

1forn1

2forn3

3forn5

6forn7

0 otherwise

n=

=

=

=

=

R

S

|

|

T

|

|

Determine an*bn.

Sol. Let, cn = an*bn =

abknk

k

n

−

=

∑

0

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

For n = 1, c 1 = abkk 1

0

1

∑ − = a 0 b 1 + a 1 b 0 = 1.1 + 1.0 = 1

For n = 2, c 2 = abkk 2

0

2

∑ − = a 0 b 2 + a 1 b 1 + a 2 b 0 = 1.0 + 1.1 + 1.0 = 1

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.2 + 0 + 1.1 + 0 = 3

For n = 4, c 4 = abkk 4

0

4

∑ − = a 0 b 4 + a 1 b 3 + a 2 b 2 + a 3 b 1 + a 4 b 0 = 0 + 1.2 + 0 + 1.1 + 0 = 3