Mathematical Foundation of Computer Science

THIS PAGE IS BLANK ...

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 2.1 Introduction............................................................ ...

2.1 INTRODUCTION In Chapter 1 we have studied that function is a process of transformation of objects from one form to other. Th ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 27 Since 1322.5 + 1322.5 (1 + 18/100)5 = 1322.5 + 1322.5 (1.18)5 = Rs ...

DHARM 28 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 2.3. Add the numeric functions an = 0for0n5 32forn6n ≤≤ +≥ R S T − ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 29 Example 2.6. Let an be a numeric function such that an is equal to ...

DHARM 30 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Similarly we define numeric function S–I an, i.e., S–I an = an + I for n ≥ ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 31 Example 2.8. Let an be a numeric function s.t. an = RS1for0n503 for ...

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 ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 33 Thus, S–1 (∇an) = S–1 (an – an–1) = S–1 an – S–1 an–1 for n ≥ 1. ∴ ...

DHARM 34 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Sol. Recall the multiplication property of the numeric functions i.e., if a ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 35 Sol. Using the convolution formula, cn = an*bn = abknk k n − = ∑ 0 ...

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 ...

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 ...

DHARM 38 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE d 22 = ∑cckk′ 22 − 0 22 = (c 0 + c 1 + ..... + c 9 ) + c 10 + c 11 = (10.2) ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 39 To illustrate more, let numeric function, an = 7, for n ≥ 0 then it ...

DHARM 40 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE and b n n= n = = R S T 0 024 135 for even) 1 for odd) , , , ...... ( , , , ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 41 Consider other numeric functions, Let an = 10n^2 + 2n + 2; since 1 ...

DHARM 42 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE The features of asymptotic dominance of numeric function in terms of ‘Big–O ...

DHARM DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 43 or an ≤ {1/3} n^3 + O(n^2 ) Hence, an is {1/3} n^3 + O(n^2 ). Examp ...