tailieunhanh - concrete mathematics a foundation for computer science phần 2

Cung cấp chi phí-hiệu quả kết nối trang web nhỏ trong khi cung cấp dự phòng CallManager yêu cầu. Đảm bảo một con đường tăng trưởng liên tục khi một trang web nhỏ phát triển để tiêu thụ hơn mạng | FINITE AND INFINITE CALCULUS 51 In particular when m 1 we have k- k so the principles of finite calculus give US an easy way to remember the fact that n2 y k y n n 1 2 0 k n The definite-sum method also gives US an inkling that sums over the range 0 k n often turn out to be simpler than sums over 1 s k n the former are just f n f 0 while the latter must be evaluated as f n 1 f 1 Ordinary powers can also be summed in this new way if we first express them in terms of falling powers. For example k2 kà kk hence _ t13 2 y k2 jn n 1 n 2 n n - n - 1 . o k n Replacing n by n 1 gives US yet another way to compute the value of our With friends like old friend n 22o k n k2 in closed form. s-- Gee that was pretty easy. In fact it was easier than any of the umpteen other ways that beat this formula to death in the previous section. So let s try to go up a notch from squares to cubes A simple calculation shows that k3 k- 3k- k-. It s always possible to convert between ordinary powers and factorial powers by using Stirling numbers which we will study in Chapter 6. Thus as k b a Falling powers are therefore very nice for sums. But do they have any other redeeming features Must we convert our old friendly ordinary powers to falling powers before summing but then convert back before we can do anything else Well no it s often possible to work directly with factorial powers because they have additional properties. For example just as we have x y 2 X2 2xy y2 it turns out that x y - X- 2xkyl y- and the same analogy holds between x y and x y . This factorial binomial theorem is proved in exercise . So far we ve considered only falling powers that have nonnegative exponents. To extend the analogies with ordinary powers to negative exponents 52 SUMS we need an appropriate definition of X for m 0. Looking at the sequence X- x x- l x-2 X x x-l xl x V 1 x x x we notice that to get from X- to X- to X- to X- we divide by x 2 then by x - 1 then by X. It seems reasonable if not imperative