Discrete Mathematics 3

<div>Discrete Mathematics 3</div><div><br></div><div>Mathematics from high school to university</div><div><br></div><div><span style="font-size: 1rem;">[None of our courses are produced using AI; they are all real-human products.]</span></div><div><br></div><div>S1. Introduction to the course</div><div>You will learn: about this course: its content and the optimal way of studying it together with the book.</div><div><br></div><div><span style="font-size: 1rem;">S2. Some preliminaries for the sections devoted to sequences</span></div><div>You will learn: some basic algebraic techniques that are needed for the sections about sequences: solving systems of linear equations (2-by-2 and 3-by-3 determinants, Sarrus' rule, Cramer's rule), solving quadratic equations (with help of the discriminant, or by qualified guesses), some basics about polynomials, finding integer zeros of polynomials with integer coefficients, polynomial division, partial fraction decomposition, subspaces of vector spaces and their generators, span, some formulas for derivatives. [My advice is that you don't watch this section before you know why you need this stuff; I will refer to the appropriate videos when I'm about to use some of the concepts and techniques above for working with sequences.]</div><div><br></div><div><span style="font-size: 1rem;">S3. A general introduction to sequences</span></div><div>You will learn: various ways of defining sequences (by a closed/explicit formula, by recursion, a verbal description, with help of a picture, by giving a number of elements that suggest a rule), arithmetic operations on sequences ([element-wise] addition, subtraction, multiplication, scaling), sequence of partial sums, sequence of differences, the vector space of all sequences of real numbers (a preparation for S7).</div><div><br></div><div><span style="font-size: 1rem;">S4. Arithmetic progressions and arithmetic sums</span></div><div>You will learn: the definition and properties of arithmetic progressions; partial sums of an arithmetic progression; monotonicity of sequences (generally, and specifically of arithmetic progressions).</div><div><br></div><div><span style="font-size: 1rem;">S5. Geometric progressions and geometric sums</span></div><div>You will learn: the definition and properties of geometric progressions; partial sums of a geometric progression; monotonicity of geometric progressions.</div><div><br></div><div><span style="font-size: 1rem;">S6. Polynomial sequences</span></div><div>You will learn: how to deal with sequences that have constant sequence of (first, second, third, and so on) differences; you will learn that all such sequences are polynomial sequences and you will learn how to find their explicit formulas.</div><div><br></div><div><span style="font-size: 1rem;">S7. Solving linear recurrence relations</span></div><div>You will learn: solving linear recurrence relations of order k with constant coefficients (mainly homogenous, but you will also see some simple examples of non-homogenous ones); some examples of counting problems that are modelled by linear recurrences; solution sets of linear recurrences with constant coefficients as subspaces of vector spaces of all sequences numbered from index 0; linearly independent solutions (optional).</div><div><br></div><div>S8. Generating functions</div><div>You will learn: the concept of a generating function for a sequence, with some arithmetic rules for working with it, some examples of generating functions of various sequences, and two examples of application.</div><div><br></div><div>S9. Some fun problems about sequences</div><div>You will learn: OK, this section is just for fun: it shows you some really cool problems about sequences.</div><div><br></div><div><span style="font-size: 1rem;">S10. A brief introduction to Graph Theory</span></div><div>You will learn: you get a very brief and elementary introduction to Graph Theory; for this one, I recommend reading Chapter 2 from the DM Book, as the concepts are quite easy to grasp (even though the theory itself is surprisingly complicated!) and I will concentrate on some more difficult parts in the video lectures and, as always, I'll deliver plenty of illustrations; this should give you a decent preparation to a future serious course devoted entirely to Graph Theory (I have no plans to create such a course, though, so you will have to look somewhere else for it...).</div><div><br></div><div>S11. Some applications of Discrete Mathematics</div><div>You will learn: some applications of DM to CS; it will not be much, just some (very modest) words about algorithm complexity, Chinese Remainder Theorem, and RSA encryption; you get a bunch of practice problems (with solutions), both in the videos and in other resources; you will also get some advice for your further studies of DM, and all the students are welcome to leave references to their favorite resources on the QA under the last lecture in this section.</div><div><br></div><div><span style="font-size: 1rem;">Note: This is the third (and last) part of our trilogy in Discrete Mathematics.</span></div><div><br></div><div><span style="font-size: 1rem;">Make sure that you check with your professor what parts of the course you will need for your final exam. Such things vary from country to country, from university to university, and they can even vary from year to year at the same university.</span></div><div><br></div><div>A detailed description of the content of the course, with all the 181 videos and their titles, and with the texts of all the 320 problems solved during this course, is presented in the resource file</div><div><br></div><div>“001 List_of_all_Videos_and_Problems_Discrete_Mathematics_3.pdf”</div><div><br></div><div>under Video 1 ("Introduction to the course"). This content is also presented in Video 1.</div>

What you'll learn:

• How to solve problems in chosen Discrete-Mathematics topics (illustrated with 320 solved problems) and why these methods work, with step-by-step explanations.
• The concept of number sequences: how we can define them (in various way: explicitly, recursively, verbally, ...) and depict them (as functions from N to R).
• A general introduction to sequences, with illustrations, guessing their closed formulas based on various descriptions and proving closed formulas by induction.
• Famous sequences (Fibonacci sequence, triangular numbers, tetrahedral numbers, perfect squares, powers of two) and their place in Pascal's Triangle.
• Mathematical modelling and finding recursive formulas.
• Sequences of differences and sequences of partial sums.
• Arithmetic progressions and arithmetic sums.
• Geometric progressions and geometric sums.
• Monotone sequences with some examples (arithmetic and geometric progressions and their monotonicity).
• Periodic sequences with some examples (all of them based on elementary Number Theory and modulus).
• Polynomial sequences and their sequences of differences; a complete characterisation of such sequences and a method of finding their closed formula (Ansatz).
• Solving linear recursion with help of characteristic polynomials: the case of real zeros of various multiplicities; homogenous and non-homogenous.
• An introduction to generating functions for sequences.
• Some identities involving the Fibonacci numbers.
• An elementary introduction to some basic concepts in Graph Theory: isomorphic graphs, subgraphs, induced subgraphs, degree of a vertex, adjacency, cycles.
• Special graphs: trees, complete graphs K_n, paths P_n, cycles C_n, bipartite graphs, complete bipartite graphs K_(m,n), the Tutte Graph, the Petersen Graph.
• Trees and their basic properties.
• Planar graphs: Euler's Formula.
• Euler trails and circuits, Hamilton paths and cycles.
• An introduction to graph coloring; monochromatic triangles.
• Chromatic number (defined by proper vertex coloring with minimal number of colors) of certain graphs.
• Chromatic index (defined by proper edge coloring with minimal number of colors) of certain graphs.
• Relations and graphs (covered in DM1).
• A word about matching in bipartite graphs.
• Some applications of DM: Chinese Remainder Theorem, cryptography, quick arithmetic.
• Sequences in algorithms: polynomial and exponential sequences as studied in Sec. 6&7.
• Some advice for further studies of DM.