Ex05 - Cs.ioc.ee

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

Download Report