32. Prove the following stronger version of Dirichlet's approximation. If a is a real number and n is a positive integer, there are integers a and b such that 1 ≤ a ≤n and laa -bl≤ 1/(n+1). (Hint: Consider the n +2 numbers 0, . . . , {ja}, ..., 1 and the n + 1 intervals (k-1)/(n+1) < x
32. Prove the following stronger version of Dirichlet's approximation. If a is a real number and n is a positive integer, there are integers a and b such that 1 ≤ a ≤n and laa -bl≤ 1/(n+1). (Hint: Consider the n +2 numbers 0, . . . , {ja}, ..., 1 and the n + 1 intervals (k-1)/(n+1) < x
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Consider chapter 1.1, exercise 32 of “Elementary Number Theory & It’s Applications”:
Prove the following stronger version of Derichlet’s approximation. If α is a real number and n is a positive integer, there are integers a and b such that 1 ≤ a ≤ n and:
|aα-b| ≤ 1/(n+1)
The following hint was left below:
(Hint: Consider n+2 numbers 0,…,{ja},…,1 and the n+1 intervals (k-1)/(n+1) ≤ x < k/(n+1) for k=1,…,n+1.)
The original Derichlet’s Approximation Theorem and proof is shown in the first image. The current problem, #32, is shown in the second image.
![R=k+1
1.1 Numbers and Sequences
-
pe 4
Proof. If none of the k boxes contains more than one object, then the total number of
objects would be at most k. This contradiction shows that one of the boxes contains at
least two or more of the objects.
9
We now state and prove the approximation theorem, which guarantees that one of
the first n multiples of a real number must be within 1/n of an integer. The proof we
give illustrates the utility of the pigeonhole principle. (See [Ro07] for more applications
of the pigeonhole principle.) (Note that in the proof we make use of the absolute value
function. Recall that x1, the absolute value of x, equals x if x ≥ 0 and -x if x <0. Also
recall that Ix
yl gives the distance between x and y.)
Theorem 1.3. Dirichlet's Approximation Theorem. It is a real number and n is a
positive integer, then there exist integers a and b with 1 ≤ a ≤n such that aa-b<1/n
Proof. Consider the n+1 numbers 0, fat. £20...nat. These n+1 numbers
are the fractional parts of the numbers ja, i = 0, 1, ..., n, so that 0≤{ja}<1 for
j = 0, 1,..., n. Each of these n + 1 numbers lies in one of the n disjoint intervals
0≤x≤ 1/n, 1/n <x<2/n,..., (j-1)/n <x<j/n,..., (n-1)/n ≤ x < 1. Be-
cause there are n + 1 numbers under consideration, but only n intervals, the pigeonhole
principle tells us that at least two of these numbers lie in the same interval. Because each
of these intervals has length 1/n and does not include its right endpoint, we know that
the distance between two numbers that lie in the same interval is less than 1/n. It follows
that there exist integers j and k with 0≤ j<k≤n such that |{ka} - {ja}| < 1/n. We
will now show that when a = k - j, the product aa is within 1/n of an integer, namely,
the integer b = [ka] - [ja]. To see this, note that
laa -b|=|(k- j)a - ([ka] - [ja])|
= |(ka [ka])-(ja - [ja]]
= |{ka}-{ja}| < 1/n.
Furthermore, note that because 0≤j<k≤n, we have 1 ≤a=k-j≤n. Conse-
quently, we have found integers a and b with 1≤a ≤n and laa -bl < 1/n, as desired.
Example 1.6. Suppose that a = √2 and n = 6. We find that 1 √2 1.414, 2-√√2~
2.828,3√2~4.243,4 √2~5.657,5 √27.071, and 6 √28.485. Among these
numbers 5√2 has the smallest fractional part. We see that 15 √2-71~17.071-71 =
0.0711/6. It follows that when a = √2 and n = 6, we can take a = 5 and b = 7 to
< 1/n.
make aa-
bl
◄
Our proof of Theorem 1.3 follows Dirichlet's original 1834 proof. Proving a stronger
version of Theorem 1.3 with 1/(n + 1) replacing 1/n in the approximation is not diffi-
cult (see Exercise 32). Furthermore, in Exercise 34 we show how to use the Dirichle
how that, given an irrational number a, there are infinitely](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F9acf228d-ec9e-49d8-a78a-8ceb13ba5105%2Ff0692906-99c8-4a0b-a768-6be307e0d7ca%2Fv6mchs_processed.jpeg&w=3840&q=75)
Transcribed Image Text:R=k+1
1.1 Numbers and Sequences
-
pe 4
Proof. If none of the k boxes contains more than one object, then the total number of
objects would be at most k. This contradiction shows that one of the boxes contains at
least two or more of the objects.
9
We now state and prove the approximation theorem, which guarantees that one of
the first n multiples of a real number must be within 1/n of an integer. The proof we
give illustrates the utility of the pigeonhole principle. (See [Ro07] for more applications
of the pigeonhole principle.) (Note that in the proof we make use of the absolute value
function. Recall that x1, the absolute value of x, equals x if x ≥ 0 and -x if x <0. Also
recall that Ix
yl gives the distance between x and y.)
Theorem 1.3. Dirichlet's Approximation Theorem. It is a real number and n is a
positive integer, then there exist integers a and b with 1 ≤ a ≤n such that aa-b<1/n
Proof. Consider the n+1 numbers 0, fat. £20...nat. These n+1 numbers
are the fractional parts of the numbers ja, i = 0, 1, ..., n, so that 0≤{ja}<1 for
j = 0, 1,..., n. Each of these n + 1 numbers lies in one of the n disjoint intervals
0≤x≤ 1/n, 1/n <x<2/n,..., (j-1)/n <x<j/n,..., (n-1)/n ≤ x < 1. Be-
cause there are n + 1 numbers under consideration, but only n intervals, the pigeonhole
principle tells us that at least two of these numbers lie in the same interval. Because each
of these intervals has length 1/n and does not include its right endpoint, we know that
the distance between two numbers that lie in the same interval is less than 1/n. It follows
that there exist integers j and k with 0≤ j<k≤n such that |{ka} - {ja}| < 1/n. We
will now show that when a = k - j, the product aa is within 1/n of an integer, namely,
the integer b = [ka] - [ja]. To see this, note that
laa -b|=|(k- j)a - ([ka] - [ja])|
= |(ka [ka])-(ja - [ja]]
= |{ka}-{ja}| < 1/n.
Furthermore, note that because 0≤j<k≤n, we have 1 ≤a=k-j≤n. Conse-
quently, we have found integers a and b with 1≤a ≤n and laa -bl < 1/n, as desired.
Example 1.6. Suppose that a = √2 and n = 6. We find that 1 √2 1.414, 2-√√2~
2.828,3√2~4.243,4 √2~5.657,5 √27.071, and 6 √28.485. Among these
numbers 5√2 has the smallest fractional part. We see that 15 √2-71~17.071-71 =
0.0711/6. It follows that when a = √2 and n = 6, we can take a = 5 and b = 7 to
< 1/n.
make aa-
bl
◄
Our proof of Theorem 1.3 follows Dirichlet's original 1834 proof. Proving a stronger
version of Theorem 1.3 with 1/(n + 1) replacing 1/n in the approximation is not diffi-
cult (see Exercise 32). Furthermore, in Exercise 34 we show how to use the Dirichle
how that, given an irrational number a, there are infinitely
![14
The Integers
c) 1, 2, 3, 5, 7, 10, 13, 17, 21, 26
d) 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365
23. Find three different formulas or rules for the terms of a sequence {a,,} if the first three terms
of this sequence are 1, 2, 4.
24. Find three different formulas or rules for the terms of a sequence {a} if the first three terms
of this sequence are 2, 3, 6.
25. Show that the set of all integers greater than 100 is countable.
26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.
27. Show that the set of all numbers of the form a + b√2, where a and b are integers, is countable,
*28. Show that the union of two countable sets is countable.
*29. Show that the union of a countable number of countable sets is countable.
30. Using a computational aid, if needed, find integers a and b such that 1 ≤a ≤ 8 and laa -b|<
1/8, where a has these values:
a) √2
b) 3/2
с) л
d) e
31. Using a computational aid, if needed, find integers a and b such that 1 ≤ a ≤ 10 and laa -
b< 1/10, where a has these values:
a) √3
b) 3/3
c) 7²
d) e³
32. Prove the following stronger version of Dirichlet's approximation. If a is a real number
and n is a positive integer, there are integers a and b such that 1≤a ≤n and laa -b|≤
1/(n+1). (Hint: Consider the n + 2 numbers 0,..., {ja},..., 1 and the n + 1 intervals
(k-1)/(n+1) < x <k/(n+1) for k = 1,..., n + 1.)
33. Show that if a is a real number and n is a positive integer, then there is an integer k such that
la-n/k| ≤ 1/2k.
34. Use Dirichlet's approximation theorem to show that if a is an irrational number, then there are
infinitely many positive integers q for which there is an integer p such that la- p/q| ≤ 1/q².
35. Find four rational numbers p/q with √2-p/q|≤ 1/q².
36. Find five rational numbers p/q with 5-p/ql ≤ 1/q².
37. Show that if a = a/b is a rational number, then there are only finitely many rational numbers
p/q such that p/qa/bl < 1/q².
The spectrum sequence of a real number a is the sequence that has [na] as its nth term.
Qui
38. Find the first ten terms of the spectrum sequence of each of the following numbers.
a) 2
b) √2
c) 2+ √2
d) e
e) (1 + √5)/2
39. Find the first ten terms of the spectrum sequence of each of the following numbers.
c) (3+√3)/2 d) л
a) 3
b) √3
40. Prove that if a #ß, then the spectrum sequence of a is different from the spectrum sequence
of ß.
** 41. Show that every positive integer occurs exactly once in the spectrum sequence of a or in
the spectrum sequence of ß if and only if a and 8 are positive irrational numbers such that
1/x + 1/8 = 1.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F9acf228d-ec9e-49d8-a78a-8ceb13ba5105%2Ff0692906-99c8-4a0b-a768-6be307e0d7ca%2F5b3gpn8_processed.jpeg&w=3840&q=75)
Transcribed Image Text:14
The Integers
c) 1, 2, 3, 5, 7, 10, 13, 17, 21, 26
d) 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365
23. Find three different formulas or rules for the terms of a sequence {a,,} if the first three terms
of this sequence are 1, 2, 4.
24. Find three different formulas or rules for the terms of a sequence {a} if the first three terms
of this sequence are 2, 3, 6.
25. Show that the set of all integers greater than 100 is countable.
26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.
27. Show that the set of all numbers of the form a + b√2, where a and b are integers, is countable,
*28. Show that the union of two countable sets is countable.
*29. Show that the union of a countable number of countable sets is countable.
30. Using a computational aid, if needed, find integers a and b such that 1 ≤a ≤ 8 and laa -b|<
1/8, where a has these values:
a) √2
b) 3/2
с) л
d) e
31. Using a computational aid, if needed, find integers a and b such that 1 ≤ a ≤ 10 and laa -
b< 1/10, where a has these values:
a) √3
b) 3/3
c) 7²
d) e³
32. Prove the following stronger version of Dirichlet's approximation. If a is a real number
and n is a positive integer, there are integers a and b such that 1≤a ≤n and laa -b|≤
1/(n+1). (Hint: Consider the n + 2 numbers 0,..., {ja},..., 1 and the n + 1 intervals
(k-1)/(n+1) < x <k/(n+1) for k = 1,..., n + 1.)
33. Show that if a is a real number and n is a positive integer, then there is an integer k such that
la-n/k| ≤ 1/2k.
34. Use Dirichlet's approximation theorem to show that if a is an irrational number, then there are
infinitely many positive integers q for which there is an integer p such that la- p/q| ≤ 1/q².
35. Find four rational numbers p/q with √2-p/q|≤ 1/q².
36. Find five rational numbers p/q with 5-p/ql ≤ 1/q².
37. Show that if a = a/b is a rational number, then there are only finitely many rational numbers
p/q such that p/qa/bl < 1/q².
The spectrum sequence of a real number a is the sequence that has [na] as its nth term.
Qui
38. Find the first ten terms of the spectrum sequence of each of the following numbers.
a) 2
b) √2
c) 2+ √2
d) e
e) (1 + √5)/2
39. Find the first ten terms of the spectrum sequence of each of the following numbers.
c) (3+√3)/2 d) л
a) 3
b) √3
40. Prove that if a #ß, then the spectrum sequence of a is different from the spectrum sequence
of ß.
** 41. Show that every positive integer occurs exactly once in the spectrum sequence of a or in
the spectrum sequence of ß if and only if a and 8 are positive irrational numbers such that
1/x + 1/8 = 1.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 1 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
