Mathematical Foundations: Bounding Summations and Series

Slide Note

Explore the mathematical foundations of bounding summations, including the sum of first n natural numbers and geometric series. Learn about bounding each term of series, monotonically increasing and non-decreasing functions, and approximating summations by integrals. Dive into proofs, examples, and applications in computer science.

birkett_r Follow

Uploaded on Sep 25, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Mathematical Foundations (Bounding Summations) Neelima Gupta Department of Computer Science University of Delhi ngupta@cs.du.ac.in people.du.ac.in/~ngupta

Sum of first n natural numbers n = k 1 k Where have we encountered this series? What does it add upto? 1) n(n+ ? 2 How do you prove it? By Induction

Geometric Series rk , r < 1 Where have we encountered such a series? Remember, median of medians? T(n) <= T(2n/10) + T(7n/10) + n What is it bounded by? Is it <= 2n? How do you prove it? By Induction

Bounding each term of Series n = k we have , ( ) k 1 k , n = k for all k, hence = n n ) ( n n 2 ( ) k = 1 1 k n n k = k = log( = = n ) ! (log ) (log ) log k n n n 1 1 In general : n n max i = = . where , { } a n a a a max max k i 1 = 1 k

Doesnt work always Example : = 2 3 x x x + + + + x e 1 .......... ! 1 ! 2 ! 3 r x = r = ! r 0 = 1 . max= . 1 a ( Here, Bounding each term by amax gives us Hence, for a tighter bound, we need other techniques

Monotonically Increasing Functions A function f is said to be monotonically increasing, if for all x and y such that x y one has f(x) < f(y), so f maintains the order. Thanks Swati Mittal Roll no. 45 (MCA 2012)

Monotonically Non- Decreasing Functions A function f is said to be monotonically non- decreasing, if for all x and y such that x y one has f(x) f(y). Thanks Swati Mittal Roll no. 45 (MCA 2012)

Approximating Summation By Integrals Let f(k) be a monotonically increasing function, we can approximate it by integrals as follows: n + 1 n n = k ( ) ( ) ( ) f x dx f k f x dx 1 m m m Lets prove this first! Thanks Swati Mittal Roll no. 45 (MCA 2012)

Y F( x) F(n-1) F(n) F(m+1) F(m) mm+ n- 1nn+ X m- 1 n-2 1 1m+ n + 1 n = k ( ) ( ) f k f x dx 2 m m Thanks Swati Mittal Roll no. 45 (MCA 2012)

Y F( x) F(n-1) F(n) F(m+1) mm+ F(m) n- 1nn+ X m- 1 n-2 1 1m+ 2 n n = k ( ) ( ) f x dx f k 1 m m Thanks Swati Mittal Roll no. 45 (MCA 2012)

Monotonically Decreasing Functions A function f is said to be monotonically decreasing, if for all x and y such that x y one has f(x) > f(y) , so f reverses the order. Thanks Swati Mittal Roll no. 45 (MCA 2012)

Monotonically Non- Increasing Functions A function f is said to be monotonically non- increasing, if for all x and y such that x y one has f(x) f(y). Thanks Swati Mittal Roll no. 45 (MCA 2012)

Let f(k) be a monotonically decreasing function prove: n + 1 n n = k ( ) ( ) ( ) f x dx f k f x dx 1 m m m Thanks Swati Mittal Roll no. 45 (MCA 2012)