Exercises from Section 1.2.9
Tord M. Johnson
May 9, 2021
1. [M12] What is the generating function for the sequence
?
Let be the generating
function for the sequence .
Then
2.
[M13] Prove Eq. (11).
Proposition. .
Proof. Let
be an arbitrary nonnegative integer, and
,
two arbitrary sequences. We must show that
|
But
as we needed to show. □
3. [HM21] Differentiate the generating function (18) for
, and compare this with
the generating function for .
What relation can you deduce?
If we differentiate the generating function for the harmonic numbers
,
Eq. (18),
|
we find that
The generating function for
is
Then,
in agreement with Eq. 1.2.7-(8).
4. [M01] Explain why Eq. (19) is a special case of Eq. (21).
Eq. (19),
is a special case of Eq. (21),
|
for . Then,
since ,
5. [M20] Prove Eq. (23) by induction on .
Proposition. .
Proof. Let
be an arbitrary nonnegative integer. We must show that
|
If ,
Then, assuming
|
we must show
|
But
as we needed to show. □
6.
[HM15] Find the generating function for
differentiate it and express the coefficients in terms of harmonic numbers.
The generating function for
is
Differentiating, we find
Then,
And so,
|
for .
7. [M15] Verify all the steps leading to Eq. (38).
Suppose that we have
numbers
and we want the sum
|
expressed in terms of ,
where
the sum of th
powers. First, we establish the identity
|
If ,
Then, assuming
|
we must show
|
But
as we needed to show. Now let
Then
Taking the logarithm yields
Finally,
and hence Eq. (38).
8. [M23] Find the generating function for ,
the number of partitions of .
The number of partitions
corresponds to the number of solutions of the equation
, where
is the number of
s in the partition.
For example, for ,
The generating function for
is therefore obtained by making all possible combinations from
to
available through multiplication, so that the coefficient is the sum count of these combinations, as
|
For example, for ,
So,
That is,
______________________________________________________________________________________________________________________________
[G. Pólya, Induction and Analogy in Mathematics (Princeton: Princeton University Press, 1954),
Chapter 6]
9. [M11] In the notation of Eqs. (34) and (35), what is
in terms
of ,
,
, and
?
Suppose that we have
numbers
and we want the sum
|
expressed in terms of ,
where
the sum of th powers.
In particular, .
But
10.
[M25] An elementary symmetric function is defined by the formula
|
(This is the same as
of Eq. (33), except that equal subscripts are not allowed.) Find the generating function for
, and express
in terms of the
in Eq. (34). Write
out the formulas for ,
,
, and
.
Suppose that we have
numbers
and we want the elementary symmetric function
|
expressed in terms of ,
where
the sum of th
powers. First, we establish the identity
|
If ,
Then, assuming
|
we must show
|
But
as we needed to show. Now let
Then
Taking the logarithm yields
Finally,
and hence
We then have
and
______________________________________________________________________________________________________________________________
[Isaac Newton, Arithmetica Universalis (1707); D. J. Struik, Source Book in Mathematics (Harvard
University Press, 1969), 94–95]
11. [M25] Equation (39) can
also be used to express the ’s
in term of the ’s:
We find ,
,
, etc. What is the
coefficient of in this
representation of ,
when ?
From Eq. (39),
for ;
or equivalently,
Note that for ,
By the multinomial theorem ,
Eqs. 1.2.6-(42) and 1.2.6-(41),
Hence,
That is, the coefficient of
in this representation of ,
when
is
|
______________________________________________________________________________________________________________________________
[Albert Girard, Invention Nouvelle en Algébre (Amsterdam: 1629)]
12. [M20] Suppose we have
a doubly scripted sequence
for ; show how this
double sequence can be represented by a single generating function of two variables, and determine the generating function
for .
Given a sequence
for ,
we find the generating function to be
13. [HM22] The Laplace transform of a function
is the function
Given that
is an infinite sequence having a convergent generating function, let
be the step function
. Express the Laplace
transform of in terms of
the generating function
for this sequence.
Given the step function
and generating function
of
as
we have that
14. [HM21] Prove Eq. (13).
We may prove Eq. (13).
Proposition. .
Proof. Let and
be arbitrary
integers such that ,
and let . If
is the generating
function for ,
we must show that
|
But given
and the sum of the geometric progression for
restricted
such that ,
and hence the result. □
______________________________________________________________________________________________________________________________
[exercise 1.2.6-38]
15. [M28] By considering ,
find a closed form for the generating function
|
In the case that ,
we have that
and in the case that ,
we have that
That is, in either case,
|
Then,
so that
or equivalently, so that
Then, if ,
if and only if
|
and if ,
so that for ,
Hence, for ,
|
16. [M22] Give a simple formula for the generating function
, where
is the number of
ways to choose
out of
objects, subject to the condition that each object may be chosen at most
times. (If
, we have
ways,
and if ,
we have the number of combinations with repetitions as in exercise 1.2.6-60.)
We want to find ,
the number of ways to choose
out of
objects, subject to the condition that each object may be chosen at most
times.
Letting
be the formal parameter of our generating function
,
the number of ways to choose an object zero times is
;
the number of ways to choose an object one time is
; and the number of
ways to choose an object
times is .
That is, .
For
classes of objects, this is then given by the generating function
|
In the case that ,
we have that
|
or equivalently that ;
and in the case that ,
as shown in exercise 1.2.6-60, or equivalently that
for
,
.
________________________________________________________________________________
[exercise 1.2.6-60]
17. [M25] What are the coefficients of
if this function is expanded into a double power series in terms of both
and
?
We have
18. [M25] Given
positive integers and
, find a simple formula for the
value of the following sums: (a) ;
(b) . (For
example, when
and the sums
are, respectively,
and .)
We may find simple formulas for the sums, given positive integers
and
.
-
a)
- For
we have
so that the formula is given by
|
-
b)
- For
we have
so that the formula is given by
|
19. [HM32] (C. F. Gauss, 1812.) The sums of the following infinite series are well known:
|
|
Using the definition
found in the answer to exercise 1.2.7-24, these series may be written respectively as
|
Prove that, in general,
has the value
|
where and
are integers
with .
[Hint: By Abel’s limit theorem the sum is
|
Use Eq. (13) to express this power series in such a way that the limit can be evaluated.]
Proposition.
has the value
|
when
and
are integers with .
Proof. As a preliminary identity, observe that
Let be artibtrary
integers such that ,
and define
as
for any nonnegative rational number
.
We must show that
|
We have
|
By Abel’s limit theorem,
|
Then,
For the left sum,
For the right sum with ,
That is,
|
Continuing in the limit as ,
The limit of the first term is
and the limit of the remaining terms of (19.2) is
|
but
and
Finally,
Hence,
|
as we needed to show.
□
______________________________________________________________________________________________________________________________
[exercise 1.2.7-24; C. F. Gauss, §33 of his monograph on hypergeometric series, Eq. [75]; Abel, Crelle 1
(1826), 314–315]
20. [M21] For what coefficients
is ?
First, observe that multiplying both sides of Eq. (20) by
yields
We then have
so that
21. [HM30] Set up the generating function for the sequence
and
study properties of this function.
Let
be the generating function for the sequence .
Given the recurrence
we have that
This is the ordinary differential equation
|
satisfied by
|
for the exponential integral
and constant ;
that is,
|
since
and
This generating function diverges, as may be verified using the root test, since for positive
,
is unbounded.
________________________________________________________________________________
[K. Knopp, Infinite Sequences and Series (Dover, 1956), Section 66 [sic]]
22. [M21] Find a generating function
for which
|
As a preliminary, observe that if
is an arbitrary complex number such that ,
we have that
since
Now, for the given sum,
|
we may generate the
terms for all
using the binomial theorem as
and then multiply them together to arrive at the equivalence
That is, the generating function is
Incidentally,
23. [M33] (L. Carlitz.) (a) Prove that for all integers
there are
polynomials
and
such that the formula
|
is an identity for all integers .
(b) Generalizing exercise 15, find a closed form for the sum
|
in terms of the functions
and in
part (a).
(c) Find a simple expression for
when .
The answers to exercise 23 follow below.
-
(a)
- We may prove the identity.
Proposition. For all integers
there are
polynomials
and such that
for all integers ,
Proof. Let
be an arbitrary positive integer. We must show that there are polynomials
and
such that for
all integers ,
We proceed with a proof by induction on
.
In the case that ,
let
and .
Then we must show in this case that
If ,
Then, assuming
|
we must show that
|
But
As our inductive hypothesis, we assume that there are polynomials
and
such that for
all integers ,
We must show that there are polynomials
and
such that for
all integers ,
But, set ,
and let
Then
This is what we needed to show. □
Note that
obeys the recurrence
|
since ,
and if ,
then
and similarly
the recurrence
|
since ,
and if ,
then
-
(b)
- We want to find a closed form for the sum
|
in terms of the functions
and
of part (a). But
Then,
and, by Eq. (20),
Let
and
Then, since
we find
-
(c)
- When , we
may simplify .
In the case ,
satisfied by
and in the case ,
since
and
we find in general that
That is,
______________________________________________________________________________________________________________________________
[exercise 1.2.8-30; L. Carlitz, Collectanea Math. 27 [sic] (1965), 281–296]
24. [M22] Prove that, if
is any generating function, we have
|
Evaluate both sides of this identity when
is (a) ; (b)
.
Proposition. .
Proof. Suppose
is an arbitrary generating function,
We must show that
|
But by a rule of the coefficient of
operator ,
as we needed to show. □
-
(a)
- For ,
and
-
(b)
- For ,
and
since
25. [M23] Evaluate the
sum by simpliyfing the
equivalent formula .
We have
______________________________________________________________________________________________________________________________
[G. P. Egorychev, Integral Representation and the Computation of Combintatorial Sums (Amer. Math.
Soc., 1984)]
26. [M40] Explore a generalization of the notation (31) according to which we might write, for example,
when
is given
by (1).
n.a.
________________________________________________________________________________
[D. E. Knuth, A Classical Mind (Prentice-Hall, 1994), 247–258]