Mathematical Foundation of Computer Science

DHARM

34 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Sol. Recall the multiplication property of the numeric functions i.e., if an and bn are two nu-
meric functions then anbn will also be a numeric function.
So, anbn = (n + 1). an for n ≥ 0
= cn (let)
Now ∆(anbn) = ∆(cn) = cn+1 – cn for n ≥ 0
= (n + 2) an+1 – (n + 1) an
= an (an – n + 2a – 1) for n ≥ 0.
Example 2.14 Let cn = an. bn, then show that cn = an+1 (∆bn) + bn(∆an).
Sol. From the definition of forward difference ∆cn = cn+1 – cn for n ≥ 0,
where cn+1 will be an+1. bn+1 so
∆cn = an+1. bn+1 – an. bn for n ≥ 0
= an+1. bn+1 – an+1. bn – an. bn + an+1. bn
= an+1 (bn+1 – bn) + bn (an+1 – an)
= an+1 (∆bn) + bn (∆an)
RHS
Example 2.15 Let an and bn are two numeric functions let dn = an/bn is another numeric
function (whose value at n is equal to the quotient of an/bn), then show that
∆dn = {bn (∆an) – an(∆bn)}/bn bn+1.
Sol. From the definition of forward difference of numeric function dn we have,
∆dn = dn+1 – dn for n ≥ 0
Since we havedn = an/bn, so dn+1 = an+1/bn+1
Therefore, ∆dn = an+1/bn+1 – an/bn LHS
= {an+1 bn – an bn+1}/bn bn+1
= {an+1 bn – an bn + an bn – an bn+1}/bn bn+1
= bn {an+1 – an} – an {bn+1 – bn}/bn bn+1
= {bn (∆an) – an (∆bn)}/bn bn+1
RHS
2.2.9 Let an and bn are two numeric functions then convolution of an and bn, is denoted as
anbn is a numeric function and it is defined as,
anbn = a 0 bn + a 1 bn–1 + a 2 bn–2 + ............... + ak bk–1 + ........ + an–1 b 1 + an b 0

= abknx

k

n

−

=

∑

0

which is a numeric function let it be cn.

For example, let an = pn for n ≥ 0

bn = qn for n ≥ 0

Then convolution of an & bn will be given as,

an*bn = pqknk

k

n

−

=

∑

0

Example 2.16 Let an and bn are two numeric functions i.e.,

a for n

n for n

= ≤≤

≥

R

S

T

10 2

03 and

b 1for0 n 2

n 0forn 3

= ≤≤

≥

R

S

T

Determine an*bn.