Homework assignments
(MATH 3166-001, Spring 2025)
Instructor: Gábor Hetyei Last update: Thursday, March 27, 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:
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).