Solutions to More problems

The second exam (Tuesday before Thanksgiving) will be over generating functions, counting problems, and complex numbers. Here are some questions to work on in preparation.

1. The generating function for a seqence is . Find the sequence.

Solution: for some a and b (we'll find them later).

=

So . Now going back to find a and b. f(0) = 1 = a + b and f(2) = . Solve to get hey are both

2. Suppose is the sequence defined recursively by for n > 0, . Find a closed formula for .

Solution:

=

So, = since .

Solve for f(x) = = for some a and b.

so

=

3. Suppose is the sequence defined recursively by , , and for n > 1, . Find a closed formula for .

= 1

= =

>

> convert(1/((1+x)*(1-2*x)),parfrac,x);

So

4. Prove that

5. Find the coefficient of in

Solution. Work this by brute force, listing all the solutions. First count those using the first term from the last factor (get 6), then the second term (get 5) , then the 3rd (get 4) for a total of 15. Checking with Maple,

> (x+x^3+x^5+`...`)*(x^0+x^2+x^4+x^6+x^8+`...`)*(x+x^3+x^5)=expand( (x*add(x^(2*i),i=0..6))*add(x^(2*j),j=0..6)*(x+x^3+x^5))+`..`;

>

>

6. Suppose food baskets with 12 items of three kinds (canned goods, root crops, and meats) are to be made up for Thanksgiving. Each basket must have an odd number of cans (green beans, cranberry sauce, etc), an even number of potatoes, turnips etc, and an odd number of instances of meat (but no more than 5 pieces). If no family is to receive the same type of basket (that is, no two baskets have the same number of each kind of food), how many families could get a basket this halloween?

Solution. Set up a generating function for this problem using the polynomial in problem 5. Each term in the uncollected expansion corresponds to a type of food basket. So there will be only 15 families.

7. Find the number of positive solutions to .

Solution: Write down the series product and argue that the coefficient of is the answer we seek. For the coefficient of is the number of terms in the (uncollected) expansion of the product with exponent . Each one of those terms corresponds to a sequence of 3 choices , , and of terms from the 3 factors of the series product such that the exponents add to n. So we can compute any given with Maple. Say we wanted the number of positive solutions to x + 3*y + 5*z = n for n from 1 to 100.

> a := n-> coeff( add(w^i,i=1..n)*add(w^(3*j),j=1..(iquo(n,3)+1))*add(w^(5*k),k=1..(iquo(n,5)+1)),w,n);

> seq([l,a(l)],l=1..100);

So for example, there are 298 positive solutions to x + 3*y + 5*z = 99.

Now we can go further here and get a generating function for this problem

= . In theory, we would get the partial fractions decomposition of this rational function of w, expand each term into a nice series with closed form nth term and then add these to get the closed form for . However, this is only a review sheet and I can promise you that I will not ask you to do this on the exam.

> convert(1/((1-w)*(1-w^3)*(1-w^5)), parfrac,w);

>

>

8. Compute and express in the form or . Draw them on a coordinate graph.

a) b) c) The sum of all the Gaussian integers , with i and j between 0 and n.

d) the square roots of 1+ I e) the 5th roots of 1. f) the sum of the positive powers of .

Solution: We did most of these in class thursday. I will check with maple.

b)

> seq(evalc((1+I)^i),i=1..10);

c)

> i := 'i': j := 'j': Sum(Sum(i+I*j,j=0..n),i=0..n)=factor( sum(sum(i+I*j,j=0..n),i=0..n));

d)

> `+/-`*sqrt(1+I) = `+/-`*evalc(sqrt(1+I));

In polar form the square roots of 1 + I are

> readlib(polar);

> polar(evalc(sqrt(1+I)));

e)

> solve(z^5-1,z);

In polar form the 5th roots of 1 are as i goes from 0 to 4.

f)

> Sum(1/10*(1+I)^i,i=1..infinity) = sum(1/10*(1+I)^i,i=1..infinity);

>

9. a) Solve for z. b) Find the imaginary part of the conjugate of , where .

c) Solve for z by completing the square. Express the roots in the form

Solution. a) = b) = , so imaginary part of conjugate is I c) , so , so . Write -3 + I = so sqrt(-3+I) = , and so

.

Checking with Maple.

> evalc((3-I)/(2+I));

> evalc(cos(Pi-arctan(1/3))+I*sin(Pi-arctan(1/3)));

> evalf(evalc(sqrt(sqrt(10))*(cos(Pi/2-arctan(1/3)/2)+I*sin(Pi/2-arctan(1/3)/2)))-I);

> fsolve(z^2+2*I*z + (2-I),z,complex);

We did it right!

10. Show that if p(z) is a polynomial with real coefficients then the non-real roots of p(z) occur in conjugate pairs: that is, if then . Prove the converse, if its true.

Solution. Let , where all the 's are real. If p(r) = 0, then . But

= ,

so is also a root of p. The converse is true. To see it, use the fundamental theorem to write p as a product of linear factors . We pair off the factors where is nonreal and multiply them out . Note that the coefficients of these quadratic factors of p are real. Hence p can be written as times a product of linear factors with real coefficients times a product of quadratic factors with real coefficients. Thus p has real coefficients.

11. Suppose p(z) is a polynomial such that if , then . Show that the polynomial has real coefficients.

Solution.

Note that if is a root of q, then is a root of p. By the property of p, is a root of p. But and so is a root of q. So q has real coefficients by the converse of 10.

12. Must a quadratic polynomial with real fixed points have real coefficients?

Solution. As we discussed in class, this is like asking if a quadratic polynomial with real roots must have real coefficients. Let and be the roots of . By the factor theorem, = . Upon inspection, we see that and are real only when a is real. But of course, we can easily make up a counterexample to that. Let 1 and 2 be the fixed points and take a = I, then = has real roots and so is a polynomial with real fixed point and no real coefficients (that's overkill, we only needed that one of the coefficients is not real)

13. Show every cubic polynomial has at least one real fixed point.

Solution. As discussed in class, this is false unless the coefficients are required to be real. has for its fixed points the roots of , which are the 3 cube roots of I, which are I times the 3 cube roots of 1, none of which are real.

On the other hand, suppose the coefficients of a cubic are real. We can assume a > 0. Restrict z to the real axis. As , goes to also. Similarly, . So, for some real numbers z[1] and z[2], we have and . Since p is continuous on the interval from to , the intermediate value theorem says that p(z) = 0 has a solution in the interval.

14. Find the area of the image of the circle of radius 1 centered at 2+I under inversion .

Solution. We know that image is a circle, so all we need is the radius. The line contains a diameter of the circle to which gets carried to a diameter to of the image circle Computing = = . Hence the area of the image circle is .

15. Find the fixed points of considered as a Moebius map on the extended complex plane.

Solution. Set f(z) = z and solve for z. The quadratic polynomial is , and its roots are . To locate these numbers in the plane, we need to write where . Hence . So the 2 fixed points are . Note: this is a lot easier if you use Maple to check:

> argument(7+4*I);

>

> fsolve(z^2-(2+I)*z -1,z,complex);

Well, we computed them correctly by hand.

>

16. Show that every Moebius map has at least one fixed point (when considered as a map on the extended plane).

Solution: Let the map be . If , then there are two complex fixed point as per problem 15. If c = 0, then is a fixed point.

> solve((a*z+b)-z*(c*z+d),z);

> a^2-2*a*d+d^2+4*c*b;

>

17 Which Moebius maps have only 1 fixed point?

Solution. The translations all have only as a fixed point. If = 0 there will be only one complex fixed point.