Mathematical Foundation of Computer Science

DHARM

32 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

So determine an+1 for n ≥ 0,

• Since an = 0 for 0 ≤ n ≤ 7, so an+1 = 0 for 0 ≤ n+1 ≤ 7 or 0 ≤ n ≤ 6.


• Also an = 1 for n ≥ 8, so an+1 = 1 for n + 1 = 8 or n ≥ 7.
  Therefore,

∆a

n

n

n

n=

−= ≤≤

−= =

−= ≥

R

S

|

T|

000 0 6

10 1 7

110 8

for

for

for

Now to determine ∇an, we first determine an–1 for n ≥ 1, since we have

• an = 0 for 0 ≤ n ≤ 7, so an–1 = 0 for 0 ≤ (n – 1) ≤ 7 or 1 ≤ n ≤ 8, and


• an = 1 for n ≥ 8, so an–1 = 1 for n – 1 ≥ 8 or n ≥ 9
  Thus, putting these values in the definition of ∇an we obtain,

∇=

≤≤

=

≥

R

S

|

T|

a

n

n

n

n

007

18

09

for

for

for

Example 2.10 Let a

0 for 0 n 2

n 25forn3n

=

≤≤

+≥

R
S
T −
Determine ∆an and ∇an.
Sol. Using definition of forward difference (∆an), we have
∆an = an+1 – an for n ≥ 0
We determine ∆an+1 for n ≥ 0, using

• an = 0 for 0 ≤ n ≤ 2, so an+1 = 0 for 0 ≤ n + 1 ≤ 2 or 0 ≤ n ≤ 1, and


• an = 2–n + 5 for n ≥ 3, so an+1 = 2–(n+1) + 5 for n + 1 ≥ 3 or n ≥ 2.
  Therefore,

∆a

n

n

n

n

nn n

=

−= ≤≤

+−= =

+− −=− ≥

R

S

|

T|

−

−+ − −+

000 1

250418 2

25252 3

3

11

for 0

for

for

/

() ()

Now From the definition of backward difference (∇an), we have

∇=

=

−≥

R

S

T −

a

an

n aann n

0

1

0

1

for

for

So, find an–1 for n ≥ 1, from given an,

• an = 0 for 0 ≤ n ≤ 2, so an–1 = 0 also for 0 ≤ n – 1 = 2 or 1 ≤ n ≤ 3, and


• an = 2–n + 5 for n ≥ 3, so an–1 = 2–(n–1) + 5 for n – 1 ≥ 3 or n ≥ 4.
  Therefore,

∇=

−= ≤≤

+−= =

+− −=− ≥

R

S

|

T|

−

−−− −

a

n

n

n

n

nn n

000 0 2

2 50418 3

252 52 4

3

1

for

for

for

/

()

Example 2.11 Show that S–1 (∇an) = ∆an.
Sol. LHS, since we know that ∇an = an – an–1, for n ≥ 1; and 0 for n = 0.