Concrete Mathematics

The course “ITT9132 Concrete Mathematics” is focused on the study of recurrence equations and the methods for their solution and approximation. It is primarily addressed at Doctoral and Master students of the School of Information Technology. Students from other departments who are interested in the discussed subjects are welcome to join. The course will cover several topics that have important applications in advanced computer programming and the analysis of algorithms:

1. Sums. Sums and recurrences. Manipulation of sums. Multiple Sums. General methods of summation. Finite and Infinite calculus. Infinite sums.
2. Integer Functions. Floors and ceilings. Floor/ceiling applications. Floor/ceiling recurrences. Floor/ceiling sums.
3. Number Theory. Divisibility. Prime numbers. Greatest common divisor. Primality testing. The Euler and Möbius functions.
4. Binomial Coefficients. Basic Identities. Applications. Generating functions for binomial coefficients.
5. Special Numbers. Stirling numbers of the second and of the first kind. Fibonacci numbers. Harmonic numbers. Bernoulli numbers.
6. Generating Functions. Basic maneuvers. Solving recurrences. Convolutions. Exponential generating functions.
7. Asymptotics. Big Oh notation. Big Oh manipulation. Bootstrapping. Trading tails. Euler's summation formula.

NB! This course will take place in spring semester 2024/2025 which starts on 3rd of February and ends on 16th of June (you can find that information under Start date section). The real course start and end dates will be announced at the beginning of February at the latest.

After completing this course, the student:

• combines techniques from different branches of both CONtinuous and disCRETE mathematics, including combinatorics and complex analysis;
• designs procedures to efficiently evaluate complex finite and infinite sums;
• understands the properties of several important families of numbers and applies them to solve problems of counting and estimate;
• determines explicit forms for numerical sequences defined implicitly by recurrence equations;
• provides accurate asymptotic estimates for sequences defined recursively.

Final assessment can consist of one test/assignment or several smaller assignments completed during the whole course. After declaring a course the student can re-sit the exam/assessment once. Assessment can be graded or non-graded. For specific information about the assessment process please get in touch with the contact person of this course. For specific information about grade transfer please contact your home university

The course is aimed at PhD and Master students in Computer Science, Information Technology, and related subjects. Its topics are recurrence equations and methods for their solutions, combining notions from continuous and discrete mathematics. Successful completion gives 6 ECTS credits. Prerequisites are udergraduate algebra and calculus, plus the basics of combinatorics (binomial theorem). The final grade is based on the outcome of two classroom talks, one midterm test, and one final exam, with an option for a third classroom talk for extra credit. For further information consult the web page https://www.cs.ioc.ee/~silvio/ITT9132/index.html or contact the instructor at the email address silvio.capobianco@taltech.ee

• Textbook:
• * Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics: a Foundation for Computer Science. Addison-Wesley 1994.
• Additional references:
• * Walter Rudin. Real and Complex Analysis. McGraw-Hill 1987.
• * Herbert Wilf. Generatingfunctionology. Second Edition. Academic Press 1994. Available at https://www2.math.upenn.edu/~wilf/DownldGF.html – please respect the author’s will, download only from the linked page and do not redistribute.

lectures, exercises