ITT9130 Concrete Mathematics Exercises from October 14 Silvio Capobianco Revised: October 15, 2014 Exercise 2.11 The general rule (2.56) for summation by parts is equivalent to X X (ak+1 − ak )bk = an bn − a0 b0 − ak+1 (bk+1 − bk ) , for n ≥ 0 . (1) 0≤k<n 0≤k<n Prove this formula directly by using the distributive, associative, and commutative laws. Solution. We recall the formula (2.56): ∆(uv) = u∆v + Ev∆u . By straightforward computation: X an b n − a0 b 0 = (ak+1 bk+1 − ak bk ) (telescopic sum) 0≤k<n = X ak+1 bk+1 − 0≤k<n + ak+1 bk − 0≤k<n = ak+1 bk+1 − X ak+1 bk X ak+1 bk 0≤k<n X ak+1 bk − 0≤k<n = X 0≤k<n 0≤k<n + ak bk (associativity) 0≤k<n X X X X ak b k 0≤k<n ak+1 (bk+1 − bk ) + 0≤k<n X (ak+1 − ak )bk , 0≤k<n 1 which is equivalent to (1). Exercise 2.14 Use multiple sums to evaluate n X k · 2k k=1 Solution. Write k = Pk j=1 n X 1. Then k · 2k = n k X X k=1 k=1 = = ! 1 · 2k j=1 k n X X k=1 j=1 n X n X 1 · 2k 2k j=1 k=j Clearly, n X 2k = 2j · k=j n−j X 2k k=0 j = 2 · 2n−j+1 − 1 = 2n+1 − 2j 2 Thus, n X k k·2 n X = j=1 n X k=1 = 2n+1 − 2j n+1 2 − j=1 n X 2j j=1 n+1 = n·2 −2· n−1 X 2j j=0 n n+1 − 2 · (2 − 1) = n·2 n+1 = n·2 − 2n+1 + 2 = (n − 1) · 2n+1 + 2 Alternative solution with summation by parts We must find suitable functions u(x) and v(x) such that k · 2k = u(k)∆v(k). The first things that come to our mind are u(x) = x and ∆v(x) = 2x : this choice seems convenient, because they lead to v(x) = 2x , thus Ev(x) = 2x+1 , and also ∆u(x) = 1. So: n X k k·2 = n+1 X x · 2x δ(x) 1 k=1 = x· 2x |n+1 1 − n+1 X 2x+1 · 1 δ(x) 1 n+1 = (n + 1) · 2 −2− n X 2k+1 , k=1 and the new sum is quick to compute: n X k=1 k+1 2 =4· n−1 X 2k = 4 · (2n − 1) = 2 · 2n+1 − 4 . k=0 In conclusion, n X k · 2k = (n + 1) · 2n+1 − 2 − 2 · 2n+1 + 4 = (n − 1) · 2n+1 + 2 . k=1 3 Exercise 3.2 Give an explicit formula for the integer nearest to the real number x. Do this in the two cases when an integer plus 1/2 is rounded up or down. Solution. Put x = n + t with n integer and 0 ≤ t < 1. Rounding x to the nearest integer must yield n = bxc when t < 1/2, and n + 1 = dxe when t > 1/2. This can be done by rounding x to bx + 1/2c. In fact, bx + 1/2c = bn + 1/2 + tc is n if t < 1/2, and n + 1 if t > 1/2. We also observe that bx + 1/2c = n + 1 if t = 1/2, i.e., this is the choice that corresponds to rounding up. Another option is to reason like this: Being x = bxc + {x}, rounding up means turning x into bxc if {x} < 1/2, and into dxe = bxc + 1 if {x} ≥ 1/2. Then we can just use Iverson’s brackets and round x to bxc + [{x} ≥ 1/2]. Are there any options for rounding down? We may try reasoning “by symmetry” and swapping floor with ceiling, plus with minus: that is, round x to dx − 1/2e = dn − 1/2 + te. And in fact, we immediately check that this quantity is n for t < 1/2 and n + 1 for t > 1/2. What about t = 1/2? We quickly get d(n + 1/2) − 1/2e = dne = n. So this is the function that rounds down, as required. Exercise 3.3 Let m and n be positive integers and let α be an irrational number greater than n. Evaluate bbmαc n/αc. Solution. The floor inside the floor is threatening trouble, so we should try to make it disappear. Write mα = bmαc + {mα}. Then bmαc n/α = (mα − {mα})n/α = mn − {mα}n/α By hypothesis, 1 ≤ n < α. Moreover, α is irrational, so mα is not an integer and {mα} is positive. Consequently, 0 < {mα} · (n/α) < 1 · 1. We can thus conclude that bbmαc n/αc = = = = bmn − {ma}n/αc mn + b−{ma}n/αc mn − d{ma}n/αe mn − 1 4 We make an observation of the usage of the rule bn + xc = n + bxc. This holds whatever integer n and real x are. To apply it correctly, we must keep the “plus” sign outside the floor and not change x. This means that bn − xc is n + b−xc = n − dxe, and not (in general) n − bxc. 5
© Copyright 2024 ExpyDoc