Here the 'x' is just a symbol and f or f(x) is not a function, convergence plays
But the analogy with functions of a real or complex variable is important and
useful. Addition andmultiplication of formal power series is defined as 'usual' (see
many conventions used in algebra or calculus are followed. We write, for
example, just 1
for the formal power series
We use f(0) to denote the 'constant term'
of the power series f above. The x
cannot be replaced by any other number, though it can be replaced by a formal
series h(x) with no constant term. That is, with f as above, we may consider,
This is al lowed because the computation of the coefficient of xn is a finite
any n = 0, 1, 2, ....
The notation f - g = h means f = h + g, and f/g = h means f, g and h are power
series so that f = hg.
Some of the propositions below are in Biggs, others will be discussed in class.
statements should not surprise anyone. We will not check everything.
Proposition. A power series f has an inverse 1/f (that is a power series,
of course) if
and only if f(0) ≠ 0.
The formal derivative f' for Df is defined, for f given as above, by
Proposition. For a power series f as in ( *),
Proposition. For power series f and g,
Proposition. For a power series f and an integer m, positive, negative, or zero ,
This definition coincides with that of the binomial coefficients when z is also a
Theorem (the Binomial Theorem for integral exponents ). For
an integer m,
positive, negative, or zero,
This last expression has constant term m (m - 1)(m- 2) .. (m-
k + 1). The coefficient
of xk in (1 + x)m is thus
Proposition. Let f be a power series with f(0) = 1. Then there is a unique power
series g such that g(0) = 1 and g2 = f. (We write
.) More generally,
positive integer m, there is a unique power series h so that h(0) = 1 and hm = f
we write for this h).
For f a power series with f(0) = 1 and any rational number r , we may then define
fr as after we write r = n/m with n and m integers. We should check
that it does not matter whether the fraction n/m is in lowest terms or not.
Proposition. For a power series f and a rational number r, positive, negative,
Theorem (the Binomial Theorem for rational exponents). For a rational number
r, positive, negative, or zero,
The proof is the same as that of the previous form of the
2. Catalan numbers.
The Catalan number is the number of ways to bracket or parenthesize a
of n letters, where the 'product' is a (possibly nonassociative) binary
example, there are 5 ways to evaluate abcd, namely
We have seen in class that these numbers satisfy the recursion
for n = 2, 3, : : :. It will be convenient to let
= 0 and = 1 because then
we can write
be the generating function of the Catalan numbers. The above recursion means
coefficients of xn in f and f2 are the same for all n ≥ 2. In fact, f
2 - f + x = 0.
By the quadratic formula (is this OK?),
The correct sign is '-' because f has constant term 0.
Then by the binomial theorem,
So for n ≥1, comparing the coefficient of xn on both sides of
this equation gives
3. Average number of comparisons in QUICKSORT.
Let denote the average number of comparisons the QUICKSORT algorithm re-
quires to sort n distinct numbers. We have
Multiply the above by xn-1 and sum over n = 1, 2, 3,
Let f be the generating function for the sequence
(we take to be 0). Then
the above can be written
Start solving your Algebra Problems
in next 5 minutes!
Download (and optional CD)
Click to Buy Now:
2Checkout.com is an authorized reseller
of goods provided by Sofmath
Attention: We are
currently running a special promotional offer
for Algebra-Answer.com visitors -- if you order
Algebra Helper by midnight of
you will pay only $39.99
instead of our regular price of $74.99 -- this is $35 in
savings ! In order to take advantage of this
offer, you need to order by clicking on one of
the buttons on the left, not through our regular
If you order now you will also receive 30 minute live session from tutor.com for a 1$!
You Will Learn Algebra Better - Guaranteed!
Just take a look how incredibly simple Algebra Helper is:
: Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:
Step 2 :
Let Algebra Helper solve it:
Step 3 : Ask for an explanation for the steps you don't understand:
Algebra Helper can solve problems in all the following areas:
simplification of algebraic expressions (operations
with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots
(radicals), absolute values)