Exercises from Section 1.2.3
Tord M. Johnson
February 12, 2014
1. [10] The text says that .
What then, is ?
The identities
|
imply that
|
2. [01] What does the notation
mean, if ?
The notation
if represents
the sum of all
such that , or
equivalently, .
That is,
|
3. [13] Without
using the -notation,
write out the equivalent of
and also the equivalent of
Explain why the two results are different, in spite of rule (b).
For the first notation,
|
while for the second notation,
|
The two results are different, in spite of rule (b), as
is not a permutation,
since is neither
one-to-one (
serves as a counterexample) nor onto (there is no integer
such
that ).
4. [10] Without using the -notation,
write out the equivalent of each side of Eq. (10) as a sum of sums for the case
.
For ,
the equivalent of the left side of Eq. (10) is
|
and of the right side is
|
5.
[HM20] Prove that rule (a) is valid for arbitrary infinite series, provided the series converge.
Proposition. The distributive law, for the products of sums
holds for arbitrary infinite series, provided the sums converge.
Proof. Assume that we have two infinite series
,
whose sums converge; that is, that
|
and
|
for arbitary limits ,
.
We must show that
|
But
as we needed to show. □
6. [HM20] Prove that rule (d) is valid for an arbitrary infinite series, provided that any three of the four sums
exist.
Proposition. Manipulating the domain,
is valid for arbitrary infinite series, provided that any three of the four sums exist.
Proof. Assume that
and
are arbitrary infinite series. We must show that if any three of the sums
,
,
,
exist, then we may manipulate the domain so that
.
It is sufficient to show that the convergence of three sums is sufficient for the convergence of
the fourth.
Case 1. [,
,
converge.] We must show that
converges. But if the sums ,
exist, then clearly their conjunction
exists.
Case 2. [,
,
converge.] We must sow that
converges. But if the sums ,
exist, then clearly their disjunction
exists.
Case 3. [,
,
converge.] We must show that
converges. But if the conjunction
exists, then clearly the single sum
exists.
Case 4. [,
,
converge.] We must show that
converges. But if the conjunction
exists, then clearly the single sum
exists.
Therefore, in all cases, we have shown that the convergence of three sums is sufficient for the
convergence of the fourth. □
7. [HM23] Given that
is an integer, show that ,
even if both series are infinite.
Proposition. ,
even if both series are infinite.
Proof. Assume that
is an arbitrary relation. We must show that
, even if both series
are infinite. Since
is a permutation of the integers, proving the finite case, we must show the infinite case. But
as we needed to show. □
8. [HM25] Find an example of infinite series in which Eq. (7) is false.
An example of an infinite series in which
is given by
|
for ,
.
Then
and
9. [05] Is the derivation of
Eq. (14) valid even if ?
No, the derivation for Eq. (14) is not valid if
, since the application
of rule (d) assumes .
That is, if
|
(depsite the fact that ).
10. [05] Is the derivation of Eq. (14) valid even if
?
No, the derivation for Eq. (14) is not valid if
, since the application
of rule (d) assumes .
That is, if
|
11. [03] What should the right-hand side of Eq. (14) be if
?
In the case
12. [10] What is ?
The sum
is simply a geometric progression whose closed form is given by Eq. (14) with
and
.
This yields
13. [10] Using Eq. (15) and assuming that ,
evaluate .
Since
|
we can use Eq. (15) with
and
to evaluate each term on the right-hand side as
14. [11] Using the result of the previous exercise, evaluate
.
Since ,
we can evaluate the sum as
15. [M22]
Compute the sum
for small values of .
Do you see the pattern developing in these numbers? If not, discover it by manipulations similar to those leading up
to Eq. (14).
We can manipulate the sum as
Comparing the first with the last yields
16. [M22] Prove that
|
if ,
without using mathematical induction.
Proposition.
if .
Proof. Assume that ,
.
Then
Comparing the first relation with the last, we have
|
hence we obtain the formula
as we needed to show. □
17. [M00] Let
be a set of integers.
What is ?
is the cardinality—the
number of elements—of ;
that is,
18. [M20] Show how to interchange the order of summation as in Eq. (9) given that
is the relation
“ is a multiple
of ” and
is the relation
“.”
In Eq. (9), we have
|
for
and .
In the case that
and ,
we find
and
that is, the
relation “”
and the
relation “ is
a multiple of
and .”
19. [20] What is ?
We have that
assuming .
20. [25]
Dr. I. J. Matrix has observed a remarkable sequence of formulas:
|
-
a.
- Write the good doctor’s great discovery in terms of the -notation.
-
b.
- Your answer to part (a) undoubtedly involves the number
as a base of the decimal system; generalize this formula so that you get a formula that will perhaps work
in any base .
-
c.
- Prove your formula from part (b) by using formulas derived in the text or in exercise 16 above.
The remarkable sequence of formulas observed by Dr. I. J. Matrix are analyzed below.
-
a.
- The good doctor’s great discovery in terms of the
-notation
is
|
-
b.
- The above formula may be generalized for perhaps any base
as
|
-
c.
- We may prove the above formula.
Proposition. .
Proof. Assume an arbitrary base
,
and .
We must show that
|
But
as we needed to show. □
21.
[M25] Derive rule (d) from (8) and (17).
We may derive rule (d) for manipulating the domain
|
from Eq. (8)
|
and Eq. (17)
Given that ,
as evidenced by the following table
| | | | | |
|
|
|
|
|
|
| | | | | |
| | | | | |
| | | | | |
| | | | | |
|
we have
22. [20]
State the appropriate analogs of Eqs. (5), (7), (8), and (11) for products instead of sums.
We have the following analogs for products: change of variable:
|
interchanging order of production:
|
a special case of the above:
|
and manipulating the domain:
|
23. [10] Explain why it is a good idea to define
and as zero and one, respectively,
when no integers satisify .
It is a good idea to define
and
as they are the identity elements for the operations of addition and multiplication, respectively.
This way,
and .
24. [20] Suppose that is true for
only finitely many . By induction on
the number of integers satisfying ,
prove that , assuming
that all .
Proposition.
for all .
Proof. Suppose
for .
We must show that .
If ,
clearly .
Then, assuming
|
we must show that
|
But
as we needed to show. □
25. [15]
Consider the following derivation; is anything amiss?
|
Yes. For one,
|
and for another,
|
(in fact, ).
26. [25] Show that may be
expressed in terms of by
manipulating the -notation
as stated in exercise 22.
Proposition. .
Proof. We must show that .
First note that
|
and then that
Therefore,
|
as we needed to show. □
27. [M20] Generalize the result of exercise 1.2.1-9 by proving that
|
assuming that .
Proposition.
if .
Proof. Let
for ,
.
We must show that
|
If , then
clearly .
Then, assuming
|
we must show that
|
But since ,
as we needed to show. □
28. [M22] Find a simple formula for .
We find that
29. [M30]
(a) Express
in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of
,
, and
[see Eq.
(13)].
-
a.
- We can express the sum in terms of the multiple-sum notation as
|
-
b.
- From Eq. (13) for arbitrary
we have
|
or equivalently
|
Also for arbitrary
we have that
and in the trivial case for
that
|
so that
|
and so that for
we have
equivalent to
|
We may also prove by induction that
|
If ,
clearly .
Then, assuming
|
we must show that
|
But
And so finally, we have that
|
and
Therefore,
|
30.
[M23] (J. Binet, 1812.) Without using induction, prove the identity
|
[An important special case arises when
are aribtrary complex numbers and we set ,
,
,
:
|
The terms
are nonnegative, so the famous Cauchy-Schwarz inequality
|
is a consequence of Binet’s formula.]
Proposition. .
Proof. We need to show that
|
But
as we needed to show. □
31. [M20] Use Binet’s formula to express the sum
in terms of ,
, and
.
We want to find an expression for
|
in terms of ,
, and
.
From Binet’s formula we have that
|
If we let ,
, and
,
we find
______________________________________________________________________________________________________________________________
[See Soobschch. Mat. Obschch. Khar’kovskom Univ. 4, 2 (1882), 93–98.]
32. [M20] Prove that
|
Proposition. .
Proof. We need to show that
|
If ,
clearly .
Then, assuming that
|
we must show that
|
But
as we needed to show. □
33.
[M30] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those
of exercise 20:
|
|
|
|
Prove that these formulas are a special case of a general law; let
be
distinct numbers, and show that
|
Proposition.
if
distinct.
Proof. For an arbitrary series of distinct numbers
,
, and for an
arbitrary ,
,
let
for ,
and .
By the fundamental theorem of algebra and the method of partial fractions, since
,
we have that
|
for constants ,
where
is the polynomial divisor with remainder
such that
By polynomial division, we have
|
Also, for an arbitrary ,
,
we have
Letting ,
we find
And so
or equivalently
|
letting
yields
where
and where
so that
|
That is,
|
as we needed to show. □
______________________________________________________________________________________________________________________________
Notes: Dr. Matrix was anticipated in this discovery by L. Euler, who wrote to Christian Golbach about it on 9
November 1762. See Euler’s Institutionum Calculi Integralis 2 (1769), §1169; and E. Waring, Phil. Trans. 69 (1779),
64–67
[J. J. Sylvester, Quart. J. Math. 1 (1857), 141–152.]
34. [M25] Prove that
|
provided that
and is arbitrary.
For example, if
and ,
then
|
Proposition.
provided that
and
is arbitrary.
Proof. We may prove
|
provided that
and
is arbitrary, but first we shall first prove the more general result
|
Let be the polynomial
representation of
where
|
for arbitrary coefficients .
Note that since ,
.
Then, from exercise 33, we find that
Letting
and
for ,
,
and
arbitrary, we have that
|
as we needed to show. □
35. [HM20] The notation is used to denote
the least upper bound of the elements ,
in a manner analogous to the -
and -notations.
(When is satisfied for
only finitely many ,
the notation
is often used to denote the same quantity.) Show how rules (a), (b), (c), and (d) can be adapted for manipulation of
this notation. In particular discuss the following analog of rule (a):
|
and give a suitable definition for the notation when
is satisfied for no .
We have the following analogs for the least upper bound: an additive law:
|
as well as a multiplicative law:
|
provided
and
are nonnegative; change of variable:
|
interchanging order of bound:
|
and manipulating the domain:
|
A suitable definition for the notation when
is satisfied
for no
would be
|
since
acts as the identity element for the least upper bound, in that
.
36. [M23] Show that the determinant of the combinatorial matrix is
.
Proposition. .
Proof. For
|
we must show that
|
Let
|
and
|
so that
where
|
since:
Then, since is a
triangular matrix (
whenever ),
we have that
as we needed to show. □
37.
[M24] Show that the determinant of Vandermonde’s matrix is
|
Proposition. .
Proof. For
|
we must show that
|
Let
|
and
|
so that
where
|
since:
Let
so that
and .
Then
We shall finally use this recursive identity to give a proof by mathematical induction on
.
If ,
then clearly
|
Then, assuming that
|
or equivalently that
|
we must show that
|
But
as we needed to show. □
38.
[M25] Show that the determinant of Cauchy’s matrix is
|
Proposition. .
Proof. For
|
we must show that
|
Let
|
so that
where
|
since:
Let
and
so that
|
and:
Also let
|
so that
where
|
since:
Also let
and
so that
|
and:
Then
We shall finally use this recursive identity to give a proof by mathematical induction on
.
If ,
then clearly
|
Then, assuming that
|
or equivalently that
|
we must show that
|
But
as we needed to show. □
39. [M23] Show that the inverse of a combinatorial matrix is a combinatorial matrix with the entries
.
Proposition. .
Proof. For
|
we must show that
|
Let and
so that
, and note
that .
Then
That is, for
,
or equivalently, that
|
as we needed to show. □
40. [M24] Show that the inverse of Vandermonde’s matrix is given by
|
Don’t be dismayed by the complicated sum in the numerator—it is just the coefficient of
in the polynomial
.
Proposition. .
Proof. Let
|
We must show that
|
Let ,
so that by the definition of inverse and matrix multiplication, we have
|
We require
or equivalently, given a polynomial
for
arbitrary ,
we require
with given data points .
By polynomial interpolation, expanding the polynomial to an initial but trivial
th
variable ,
with ,
in order to obtain a complete set of differences, we have
For ,
we have
|
What is left is to find the coefficients
. By de
Moivre’s work ,
we may do so.
The real and different roots of
are exactly those
where ,
since in such a case, we have
|
Let these roots be denoted by .
Since matrix multiplication with inverse is commutative, We also have
|
By de Moivre’s identities, with our trivially expanded polynomial,
we then have, since
requires
and since
and
have opposite parity, that
Therefore
|
as we needed to show. □
______________________________________________________________________________________________________________________________
[A. de Moivre, The Doctrine of Chances, 2nd edition (London: 1738), 197–199.]
41. [M26] Show that the inverse of Cauchy’s matrix is given by
|
Let
|
We must show that
|
But, by the definition of inverse,
as we needed to show.
42. [M18] What is the sum of all
elements in the inverse of the combinatorial matrix?
For the inverse of the combinatorial matrix
|
the sum of all
elements is simply
43. [M24] What is the sum of all
elements in the inverse of Vandermonde’s matrix? [Hint: Use exercise 33.]
For the inverse of the Vandermonde matrix
|
we want to find the sum of all
elements .
In the case that any ,
,
from exercise 40, we have that
|
or equivalently that
Otherwise, in the case that ,
, again from
exercise 40, given
for
we have that
|
or equivalently, for ,
that
Also, from exercise 33, we have for an extrapolated and distinct
and
for
that
|
or equivalently that
|
Similarly, if
|
This yields
Therefore, in all cases,
|
44. [M26] What
is the sum of all
elements in the inverse of Cauchy’s matrix?
For the inverse of the Cauchy matrix
|
we want to find the sum of all
elements .
But
since in general
|
from exercise 34.
Then, for some polynomial
of order
and by exercise 33
45. [M25] A Hilbert
matrix, sometimes called an
segment of the (infinite) Hilbert matrix, is a matrix for which
.
Show that this is a special case of Cauchy’s matrix, find its inverse, show that each element
of the inverse is an integer, and show that the sum of all elements of the inverse is
. [Note:
Hilbert matrices have often been used to test various matrix manipulation algorithms, because they are numerically
unstable, and they have known inverses. However, it is a mistake to compare the known inverse, given in this
exercise, to the computed inverse of a Hilbert matrix, since the matrix to be inverted must be expressed in rounded
numbers beforehand; the inverse of an approximate Hilbert matrix will be somewhat different from the inverse of an
exact one, due to the instability present. Since the elements of the inverse are integers, and since the inverse matrix
is just as unstable as the original, the inverse can be specified exactly, and one should try to invert the inverse. The
integers that appear in the inverse are, however, quite large.] The solution to this problem requires an
elementary knowledge of factorials and binomial coefficients, which are discussed in Sections 1.2.5 and
1.2.6.
The Hilbert matrix, defined as
|
is a special case of a Cauchy matrix
with
and .
As such, its inverse
has elements given by
It is clear that
is an integer, as it may be cast into binomial coefficients as
From exercise 44, the sum of the elements of the inverse is simply
______________________________________________________________________________________________________________________________
[For further information, see J. Todd, J. Research Nat. Bur. Stand. 65 (1961), 19–22; A. Cauchy,
Exercices d’analyse et de physique mathématique 2 (1841), 151–159.]
46. [M30]
Let be an
matrix, and
let be an
matrix. Given
that , let
denote the
matrix consisting
of columns
of , and let
denote the
matrix consisting
of rows
of .
Prove the Binet-Cauchy identity
|
(Note the special cases: (i) ,
(ii) , (iii)
, (iv)
, (v)
.)
Proposition. .
Proof. Let be
an matrix,
and let be
an matrix.
Given that ,
let denote the
matrix consisting
of columns
of , and let
denote the
matrix consisting
of rows
of .
We must show that
|
Let
|
for
|
be the Levi-Civita function so that in general
|
and so that if
and are identical
except that
and ,
so that
and ,
then in general
|
if are the
numbers
rearranged into nondecreasing order.
Then
as we needed to show.
Note that if ,
we have the usual identity for square matrices
|
if ,
we have the dot product
|
if ,
we have the square
|
and if ,
we have the first nontrivial case of the identity
|
□
______________________________________________________________________________________________________________________________
[J. de l’École Polytechnique 9 (1813), 280–354; 10 (1815), 29–112. Binet and Cauchy presented their
papers on the same day in 1812.]
47. [M27] (C. Krattenthaler.) Prove that
and generalize this equation to an identity for an
determinant in
variables .
Compare your formula to the result of exercise 38.
We may prove the more general equation.
Proposition. .
Proof. Let
We must show that
|
Let
|
so that
where
|
since for
Let
|
so that
|
and that
where
|
Repeating this transformation, each time over fewer columns to factor out
,
,
etc., we eventually have
|
for
|
Then let
|
so that
where
|
since for
Repeating this transformation also, each time over fewer columns to factor out
,
,
etc., we eventually have
|
for
Let
|
and
|
so that
where
|
since:
Let
so that
and .
Then
since a product of
signs will cancel with
(i.e., ).
This recursive identity allows us to prove by mathematical induction on
that
|
Therefore
as we needed to show. □
______________________________________________________________________________________________________________________________
[Manuscripta Math. 69 (1990), 177–178.]