Homework assignments
(MATH 3166-001, Spring 2025)
Instructor: Gábor Hetyei Last update: Thursday, April 17, 2025

Disclaimer: The information below comes with no warranty. If, due to typographical error, there is a discrepancy between the exercises announced in class and the ones below, or this page is not completely up to date, the required homework consists of those exercises which were announced in class. Check for the time of last update above. If, by my mistake, a wrong exercise shows up below, I will allow you extra time to hand in the exercise that was announced in class. If, however, exercises are missing because this page is not up to date, it is your responsibility to contact me before the due date. (No extra time will be allowed in that case.) This page is up to date if the last update happened after the last class before the next due date.

The deadlines do not apply to the Bonus questions, which expire only once we solve them in class, or on April 24 at latest.

Notation: In the table below, 2/18 means (supplementary) exercise 18 in section 2.

No. Date due: Problems:
12 Tue Apr 22 at noon

(Mandatory) Board problems:

  1. Write as a rational function of x.
  2. Prove by induction that the Fibonacci numbers satisfy Fn+3=2Fn+1+Fn.
  3. Using the handout on forward differences, write as a linear combination of f(n), f(n+1), ..., f(n+5).
  4. Using the method presented in the handout on forward differences, write f(n)=n3 as a linear combination of the binomial coefficients .
11 Tue Apr 15 at noon

(Mandatory) Board problems:

  1. Prove by induction that the Fibonacci numbers satisfy 3Fn=Fn+2+Fn-2 for n ≥ 2.
  2. Let Tn be the number of ways to triangulate a convex n-gon with nonintersecting diagonals. Express the number Tn in terms of the Catalan numbers. Prove your statement by stating and explaining the recurrence satisfied by the numbers Tn.
  3. Find the coefficient of xn in . Express your answer in simplest form using Catalan numbers.
  4. How many ways are there to parenthesize the product x1x2...xn ? State your answer in terms of the Catalan numbers and explain it.
  5. Write the power series as a rational function of x.

Bonus problems:

  1. Prove Napoleon's theorem, stated in the lecture notes of April 1 (B06, 8 points).
  2. Extend the definition of Fibonacci numbers to negative indices in such a way that they satisfy the same recurrence. State and prove a formula expressing the negative-indexed Fibonacci numbers in terms of the positive-indexed ones (B07, 5 points).
  3. Give a combinatorial proof of the fact that the number of partitions of n into odd parts is the same as the number of the partitions of n into distinct parts (B08, 10 points).
  4. Find the number p(n,2) of composition of n into 2 parts using generating functions (B09, 5 points).
  5. You are given n+1 copies of 1 and n-1 copies of -1 written around a circle. Prove that there is exactly one place to start summing these numbers clockwise around the circle such that the sum of the numbers added so far is always positive (B10, 5 points).
10 Tue Apr 8 at noon 8/17.

(Mandatory) Board problems:

  1. Find a ordinary generating function in which the coefficient of some power of x expresses the number of ways to purchase n bottles of soda when soda comes in packs of 6, 12 or 24. Indicate which power of x to look for.
  2. Find the ordinary generating function of for the number of nonnegative integer solutions of z1+z2+z3=15, subject to 0≤ zi≤ 8 for i=1,2,3. Also indicate the coefficient of which power of x is the answer to your question.
  3. Write a formula for the coefficient of xk in
    .
8 Tue Apr 1 at noon (Mandatory) Board problems:
  1. Find a closed form formula for the sequence given by the recurrence an+2-4an+1+4an=0 and the initial conditions a0=1 and a1=4.
  2. Find a closed form formula for the sequence given by the recurrence an+2-2an+1+2an=0 and the initial conditions a0=1 and a1=1.
8 Tue Mar 25 at noon 8/28, 29, 54.
(Mandatory) Board problems:
  1. Find the partial fraction decomposition of
    .
  2. Complete the computation of a closed-from formula of the sequence given by the recurrence an+1=-an-an-1, and by the initial conditions a0=1 and a1=0. Your answer should be a linear combination of the powers of the complex third roots of unity.
7 Tue Mar 18 at noon 5/24;  6/32;  7/18,19,22.
Board problem: Find the coefficient of xn in
.
6 Tue Mar 11 at noon 5/24;   6/32  7/18,19,22.
Board problem: Find the number of ternary strings of length 5 that have no two consecutive 1's.
5 Tue Feb 25 at noon 5/21,22;   6/26,27.

Bonus:

  1. Given a partition of n by its type vector 1m12m2...nmn, describe an algorithm that computes the type vector of its conjugate. (B04, 5 points)
  2. Write the Stirling number of the second kind S(n,n-5) as a polynomial of n. (B05, 8 points)
4 Tue Feb 18 at noon 5/18,19,27,28.
3 Tue Feb 11 at noon 4/47,51.

(Mandatory) Board problems:

  1. Find the number of ways of writing 10 as a sum of three nonnegative integers. Order matters!
  2. Find the number of ways of writing 10 as a sum of three positive integers. Order matters!
  3. Find the coefficient of x11x23x31x42 in (x1+x2+x3+x4)7.
2 Tue Feb 4 at noon 3/48, 49;   4/34,40.

(Mandatory) Board problems:

  1. Prove by induction that n < 2n holds for all positive integers n.
  2. How many ways are there to select five coins out of an unlimited supply of pennies, nickels, dimes and quarters?

Bonus: Extend Vandermonde's identity (Theorem 4.7) to the case when m and n are not integers, and are replaced with variables x and y respectively. (B03, 10 points, you may want to use that a nonzero polynomial in one variable has only finitely many roots).
1 Tue Jan 28 at noon 1/20,26;   2/28,40;   3/28,31.

(Mandatory) Board problem:

Prove by induction that 13+ 23 + ... + n3 =(1+2+...+n)2 holds for all positive integer n.

Bonus:

  1. Prove 13+ 23 + ... + n3 =(1+2+...+n)2 without using induction. (B01, 5 points).
  2. 1/28 (B02, 5 points).