Discrete Mathematics – An Open Introduction, 4th edition(discrete.openmathbooks.org)
discrete.openmathbooks.org
Discrete Mathematics – An Open Introduction, 4th edition
https://discrete.openmathbooks.org/dmoi4.html
68 comments
Discrete Mathematics and It's Applications by Kenneth H. Rosen helped me get an A in CS70 (Discrete Math and Probability) at UC Berkeley this past summer.
The textbook is quite large, but the content is very accessible. I'm also self-taught, finally taking formal math/physics coursework in my 30s to fill in the gaps.
Another amazing resource has been California Community Colleges. So far every math teacher I've had has been extraordinarily passionate. Most math classes have an async/online section, and it's pretty common for adults to take the classes just for fun/self-improvement.
The textbook is quite large, but the content is very accessible. I'm also self-taught, finally taking formal math/physics coursework in my 30s to fill in the gaps.
Another amazing resource has been California Community Colleges. So far every math teacher I've had has been extraordinarily passionate. Most math classes have an async/online section, and it's pretty common for adults to take the classes just for fun/self-improvement.
> I'm also self-taught, finally taking formal math/physics coursework in my 30s to fill in the gaps.
How did you take CS70? Are you enrolled as an undergrad/grad student?
How did you take CS70? Are you enrolled as an undergrad/grad student?
The summer session is open to the general public, and you can take courses through the Berkeley Extension during Fall/Spring on a space available basis.
https://summer.berkeley.edu/ https://extension.berkeley.edu/static/studentservices/concur...
https://summer.berkeley.edu/ https://extension.berkeley.edu/static/studentservices/concur...
[deleted]
I was intimidated by these math books, but I was able to find a lot of interesting stuff in "Applied Discrete Structures" by Al Doerr and Ken Levasseur[1]. I was attracted by the "Logic" section, and I was not disappointed. You can download it for free from their website.
> It’s a bit old and unfortunately not free
It's available on Anna's Archive, in case someone is looking for it.
[1] https://discretemath.org/
> It’s a bit old and unfortunately not free
It's available on Anna's Archive, in case someone is looking for it.
[1] https://discretemath.org/
Hey, that's my school! I didn't have Doerr or Levasseur (before my time), but James Propp did a phenomenal job of teaching the material. I don't know how discrete is taught in other schools but I thought having two dedicated classes for it was helpful.
The AOPS Counting & Probability books are shockingly good discrete math books that come with complete solutions manuals: https://artofproblemsolving.com/store
Are these good for general education? I read somewhere they were great but more geared toward math competitions.
They might be overkill, but I don't see why not. I guess it depends on what you mean by "general education".
They have great explanations of the fundamental concepts but use problems that really stretch you more than typical books.
Probably better as a second exposure, but doable as a first for a bright and motivated student.
They have great explanations of the fundamental concepts but use problems that really stretch you more than typical books.
Probably better as a second exposure, but doable as a first for a bright and motivated student.
You may also enjoy [Concrete Mathematics](https://www.goodreads.com/book/show/112243.Concrete_Mathemat...) by Graham, Knuth, Patashnik.
Concrete mathematics is significantly more advanced though, if I'm not mistaken it even introduces the basics of analytic combinatorics with OGFs.
Something at the same level would be the basic competitive math curriculum in combinatorics and number theory.
Aren't generating functions a standard part of a first course in combinatorics? They were when I took introduction to combinatorics in university.
[deleted]
I wish more textbooks, especially free resources like in the link, would be better about providing more solutions. A book with a lack of solutions tends to create a circular problem for me.
Knowing whether my solution is correct or not is dependent on how well I truly understand the concepts. However, if I truly understood the concepts, then I wouldn't need to solve the problem in the first place. How is one supposed to learn without feedback?
Knowing whether my solution is correct or not is dependent on how well I truly understand the concepts. However, if I truly understood the concepts, then I wouldn't need to solve the problem in the first place. How is one supposed to learn without feedback?
Author here. For what it's worth, deciding what percentage of the exercises should have solutions is a continual challenge. I chose to use a lot of interactive exercises (thanks to PreTeXt these are easy to embed in the text) for which students can enter their answer and get feedback on whether they are correct. That works well for computational problems. For proof-based or otherwise theoretical problems, I tired to provide enough examples with full solutions and a few exercises with them as well, while still giving those who would like to have a more authentic open-ended problem without solution that opportunity too. And of course, I want other professors to find the book useful for courses they teach, and providing problems without solutions that can be graded for credit is also important.
Anyway, hope you find the resource helpful.
Anyway, hope you find the resource helpful.
I appreciate you taking the time to respond.
The one part of your comment though I do have further questions about is:
> I want other professors to find the book useful for courses they teach, and providing problems without solutions that can be graded for credit is also important.
I would imagine if a professor could answer the problems in your book correctly without needing the solutions, then I would imagine said professors are also perfectly capable of creating their own problems with solutions. I imagine many professors probably do use the problems in back of the book for assignments, and I feel like that says a lot about the state of mathematical education.
However, I do appreciate all the effort you have put in to this textbook. I will most definitely be using it in the very near future, and I think your book is the one I am going to start with. It takes a pretty selfless person to release something of this value for free, so thank you very much.
The one part of your comment though I do have further questions about is:
> I want other professors to find the book useful for courses they teach, and providing problems without solutions that can be graded for credit is also important.
I would imagine if a professor could answer the problems in your book correctly without needing the solutions, then I would imagine said professors are also perfectly capable of creating their own problems with solutions. I imagine many professors probably do use the problems in back of the book for assignments, and I feel like that says a lot about the state of mathematical education.
However, I do appreciate all the effort you have put in to this textbook. I will most definitely be using it in the very near future, and I think your book is the one I am going to start with. It takes a pretty selfless person to release something of this value for free, so thank you very much.
Exercises without detailed solutions are useless. If I don't have direct access to a tutor I need solutions, otherwise there's no point - I can never check whether I'm right, I'm stuck, or I'm making mistakes that are invisible to me. This invalidates the whole point of a textbook, it's your entry to a field without access to a teacher.
They may be useless to you (although I think even seeing examples of types of questions that can be asked serves a purpose), but the book was not written only for you. I think it is reasonable for books to have features that are useful for students in courses that assign a grade, as well as other features that are useful for students using it for self study.
It is also worth pointing out, that at least for math textbooks, there is never an expectation that a student should solve all the exercises. If you solve those that do have a solution, then you will hopefully still have a good experience and learn lots.
It is also worth pointing out, that at least for math textbooks, there is never an expectation that a student should solve all the exercises. If you solve those that do have a solution, then you will hopefully still have a good experience and learn lots.
I've been using textbooks to learn things for over 50 years and during my development writing code many (most?) of those times was not in the context of a classroom but in the context of needing to understand something so I could write code to do it. For folks in this situation having answers, especially to some complex problems, is a huge benefit in terms of gaining understanding and saving time.
I don't think I'm alone here when I say I frequently gain understanding of things by writing code to model them. I know I understand something when I can write it in code. So after ingesting the lesson about a topic I'll see if I can write code to do what I just learned. I have spent a lot of hours stuck at a juncture of not being entirely sure my code, which works on the simple examples, is also working in the complex ones. The difference in results may not be evident. Am I troubleshooting my understanding or my code? I need a known result to actually know.
This is one place being able to copy something from your textbook, for example, paste it into ChatGPT and ask questions is a huge benefit. ChatGippity doesn't always get it right but usually the interchange is much more useful than being stuck.
I don't think I'm alone here when I say I frequently gain understanding of things by writing code to model them. I know I understand something when I can write it in code. So after ingesting the lesson about a topic I'll see if I can write code to do what I just learned. I have spent a lot of hours stuck at a juncture of not being entirely sure my code, which works on the simple examples, is also working in the complex ones. The difference in results may not be evident. Am I troubleshooting my understanding or my code? I need a known result to actually know.
This is one place being able to copy something from your textbook, for example, paste it into ChatGPT and ask questions is a huge benefit. ChatGippity doesn't always get it right but usually the interchange is much more useful than being stuck.
I find that exercises without answer help me to build confidence. It requires me to be sure of every step, and the actual answer is less relevant.
Of course this all depends on the type of exercise. For some, you can easily check the answer yourself after you have found a solution.
Also, in the real world, most assignments don't have an answer either, and it seems like a good idea to be prepared for that.
Of course this all depends on the type of exercise. For some, you can easily check the answer yourself after you have found a solution.
Also, in the real world, most assignments don't have an answer either, and it seems like a good idea to be prepared for that.
In the "real world" all assignments I had had answers. To quote a mathematics professor, "how else could I expect you to understand the material on your own, outside of my lecture".
It will help greatly if authors annotate unsolved problems with difficulty levels to let unmentored readers know what they are up against.
Yes, its painstaking for authors to provide solutions to all problems so why not let readers contribute and post their solutions ? The link to such a forum can be part of the book text.
And thank you for the superb book.
Not providing solutions is quite common in math textbooks, in part because professors (including the author!) want to be able to assign problems from the textbook to their class, and in part because making solutions is a lot of work!
Outside of a classroom setting, the way you learn from a textbook without external feedback is by engaging more actively with the material.
Treat each statement in the main text as an informal exercise. Each time you come across a proposition -- whether it's a formal theorem statement or a claim in the body of the exposition -- try proving or otherwise justifying it to yourself before reading on.
Take a look at Theorems 2.3.1 and 2.3.2 -- they are very similar. Once you have absorbed the proof of 2.3.1, you can attempt 2.3.2 on your own. If you can't finish the proof, you can read a couple of sentences from the included proof for "hints"... or, if you do finish a proof, you can compare it to the proof in the text.
If you read actively enough, you can learn the material quite well without doing any problems. Many people will claim that you need to do formal problems in order to learn math, but this is untrue. Many math textbooks at the higher level don't include formal exercises or problems at all, and people learn from them just fine.
Admittedly, reading mathematics is a skill in its own right, and you shouldn't expect it to come easily right away. Of course, the best thing is to have a one-on-one teacher, but few of us are so lucky.
Outside of a classroom setting, the way you learn from a textbook without external feedback is by engaging more actively with the material.
Treat each statement in the main text as an informal exercise. Each time you come across a proposition -- whether it's a formal theorem statement or a claim in the body of the exposition -- try proving or otherwise justifying it to yourself before reading on.
Take a look at Theorems 2.3.1 and 2.3.2 -- they are very similar. Once you have absorbed the proof of 2.3.1, you can attempt 2.3.2 on your own. If you can't finish the proof, you can read a couple of sentences from the included proof for "hints"... or, if you do finish a proof, you can compare it to the proof in the text.
If you read actively enough, you can learn the material quite well without doing any problems. Many people will claim that you need to do formal problems in order to learn math, but this is untrue. Many math textbooks at the higher level don't include formal exercises or problems at all, and people learn from them just fine.
Admittedly, reading mathematics is a skill in its own right, and you shouldn't expect it to come easily right away. Of course, the best thing is to have a one-on-one teacher, but few of us are so lucky.
I disagree. I have to learn by committing to muscle memory. I always say I'm a slow learner, but a fast thinker.
Yes, I can read/hear a concept and understand it in abstract and visualize it pretty easily, but it will leave my brain just as easily as it entered. Just the way my memory works.
Solved problems speeds up that muscle memory learning process significantly as opposed to going line by line and attempting to generate your own problems/solutions. In addition, you can solve a problem correctly, but not have the correct prose, solution manuals can help there as well.
Edit: Honestly the biggest thing about solving problems is that it gives a sense of progression and a dopamine-reward loop that most people just don't get from reading one line at a time. That being said, good problems and good solutions can be time consuming to generate, so it makes total sense to me that the PhD-level textbooks don't follow that format.
Yes, I can read/hear a concept and understand it in abstract and visualize it pretty easily, but it will leave my brain just as easily as it entered. Just the way my memory works.
Solved problems speeds up that muscle memory learning process significantly as opposed to going line by line and attempting to generate your own problems/solutions. In addition, you can solve a problem correctly, but not have the correct prose, solution manuals can help there as well.
Edit: Honestly the biggest thing about solving problems is that it gives a sense of progression and a dopamine-reward loop that most people just don't get from reading one line at a time. That being said, good problems and good solutions can be time consuming to generate, so it makes total sense to me that the PhD-level textbooks don't follow that format.
> Solved problems speeds up that muscle memory learning process significantly as opposed to going line by line
completely agree. I would recommend checking out mathacademy.com. I've been using it the last two months to raise my skill levels in math and its been a great investment of my time. It gives you a short lesson on the topic and then just gives you problem sets to burn though. what I like about it is that you don't think about your learning objectives. I just log in every day and do the problem sets and lessons until I feel like I did enough for the day. repeat everyday and you'll just naturally find yourself improving.
completely agree. I would recommend checking out mathacademy.com. I've been using it the last two months to raise my skill levels in math and its been a great investment of my time. It gives you a short lesson on the topic and then just gives you problem sets to burn though. what I like about it is that you don't think about your learning objectives. I just log in every day and do the problem sets and lessons until I feel like I did enough for the day. repeat everyday and you'll just naturally find yourself improving.
The website for math academy looks almost too good to be true. Can you describe more of your experience using it?
It’s been great for me. As of today I crossed 324 days of using it straight. I wrote about my experience here: https://gmays.com/math
And yes, I’m a total fanboy. I’ve also known the founder for over a decade and he’s been working on it for most of that time. Math Academy came out of him helping his son learn math even before that.
I haven’t found anything close to teaching math than this. It’s legit.
And yes, I’m a total fanboy. I’ve also known the founder for over a decade and he’s been working on it for most of that time. Math Academy came out of him helping his son learn math even before that.
I haven’t found anything close to teaching math than this. It’s legit.
Been using it for 3 months now. When I started, I took their placement test. its been 20 years since I had to do any difficult math so I pretty much bombed haha. It recommended their foundations 1 which is for adults returning to math after a long time.
in terms of difficulty, I found the problems to be somewhat easy. you see a set of modules on the right and your progress on the left. you click on a module to start and it gives you a written tutorial on how to solve a problem. Then you go though several of them. If you complete it with less than 3 wrong, it gives you the xp and youc an continue on another module.
if you do get 4 wrong, it stops the module and you go with the next one. usually a day or so later, it throws the lesson at you again. I've had this happen twice. usually its a sign I've been on the platform for too long for the day and my brain just can't process math anymore. Over time, it introduces more lessons and harder topics along with periodic review modules to test stuff I haven't looked at in awhile.
I'm a few days away from completing course 1 and its been a much needed review of a lot of topics I remember from algebra 2 back in highschool. One of my biggest weaknesses back then was factoring polynomials and I think mathacademy explains the process 1000x better than any of my highschool teachers did. on certain topics like factoring, i'd say I'm much stronger now than when I was in highschool.
The key is to make time for it. I view it like going to the gym. every day I set aside an hour minimum and just crank through them till I either get tired or have some other obligation I have to take care of.
Is it worth it? so far Id say its probably one of the best roi activities I've partaken in. it really does automate the process of learning math. I love that the feedback is rapid so the time between I attempt the problem and can learn from my mistakes have let me progress much faster than I could have in a classroom. you just have to make sure use it consistently. have a notebook and a calulator next to you so there's no distractions and just crank thoguh problems.
TLDR: its worth the $50 every month. As long as you're consitent with it, You WILL learn math with this program.
in terms of difficulty, I found the problems to be somewhat easy. you see a set of modules on the right and your progress on the left. you click on a module to start and it gives you a written tutorial on how to solve a problem. Then you go though several of them. If you complete it with less than 3 wrong, it gives you the xp and youc an continue on another module.
if you do get 4 wrong, it stops the module and you go with the next one. usually a day or so later, it throws the lesson at you again. I've had this happen twice. usually its a sign I've been on the platform for too long for the day and my brain just can't process math anymore. Over time, it introduces more lessons and harder topics along with periodic review modules to test stuff I haven't looked at in awhile.
I'm a few days away from completing course 1 and its been a much needed review of a lot of topics I remember from algebra 2 back in highschool. One of my biggest weaknesses back then was factoring polynomials and I think mathacademy explains the process 1000x better than any of my highschool teachers did. on certain topics like factoring, i'd say I'm much stronger now than when I was in highschool.
The key is to make time for it. I view it like going to the gym. every day I set aside an hour minimum and just crank through them till I either get tired or have some other obligation I have to take care of.
Is it worth it? so far Id say its probably one of the best roi activities I've partaken in. it really does automate the process of learning math. I love that the feedback is rapid so the time between I attempt the problem and can learn from my mistakes have let me progress much faster than I could have in a classroom. you just have to make sure use it consistently. have a notebook and a calulator next to you so there's no distractions and just crank thoguh problems.
TLDR: its worth the $50 every month. As long as you're consitent with it, You WILL learn math with this program.
Honestly, this seems needlessly painful to me. Of course, you can be scanning each sentence for a proposition, then pause, and try to reason it out, thus spending 4 weeks on like 5 pages of a 10-page chapter. But is that the best use of your time?
The bigger problem is that not every thing that the author says is within your level of reasoning. Some very simple things can be exceedingly hard to prove, and you, as a learner, don't know which is which. That's why there are the problems at the end of the chapter, which are designed for the level that you should have attained by the end of the chapter. Without solutions though, you have no way to check your understanding, and you are forced to try and squeeze every little problem from the text.
Not having solutions is simply not suitable for a self-learner. It is sufficient for a class settings, where you can ask the professor if your solution is correct.
To me, a good compromise is to provide solutions to every odd- (or even-) numbered problem. Thus, the self learners have at least half of the problems within their reach, and t he teachers can assign the other half of the problems.
The bigger problem is that not every thing that the author says is within your level of reasoning. Some very simple things can be exceedingly hard to prove, and you, as a learner, don't know which is which. That's why there are the problems at the end of the chapter, which are designed for the level that you should have attained by the end of the chapter. Without solutions though, you have no way to check your understanding, and you are forced to try and squeeze every little problem from the text.
Not having solutions is simply not suitable for a self-learner. It is sufficient for a class settings, where you can ask the professor if your solution is correct.
To me, a good compromise is to provide solutions to every odd- (or even-) numbered problem. Thus, the self learners have at least half of the problems within their reach, and t he teachers can assign the other half of the problems.
> spending 4 weeks on like 5 pages of a 10-page chapter. But is that the best use of your time?
Look at it as the best use of paper :)
Many math books are dense. They don't bullshit you around. Spending several hours on a single page is the normal usage.
Look at it as the best use of paper :)
Many math books are dense. They don't bullshit you around. Spending several hours on a single page is the normal usage.
Yeah, and for better or for worse, it is the best arrangement. I remember ploughing through Alan Baker’s number theory book. You have to sit with a pencil and paper and convince yourself of half the steps, but you sure as hell know the material afterwards. And you do need the skills you gain by doing this.
> And you do need the skills you gain by [engaging].
The slogan I've heard is: "Mathematics is not a spectator sport."
The slogan I've heard is: "Mathematics is not a spectator sport."
I haven’t heard that one before but it’s on the nose. I have heard Euclid’s much older “There is no royal road to geometry”.
> because making solutions is a lot of work!
Imagine how much more work it is to try to solve these exercises then. Exponentially more than creating solutions for someone who already mastered this topic. This tells me a lot about how a teacher thinks of students.
Imagine how much more work it is to try to solve these exercises then. Exponentially more than creating solutions for someone who already mastered this topic. This tells me a lot about how a teacher thinks of students.
> This tells me a lot about how a teacher thinks of students.
This is quite an uncharitable perspective!
This is quite an uncharitable perspective!
It comes from experience. I had several professors who did not even release the script for a course, much less the problems and never solutions - everything had to be written down by hand by students while you were supposed to listen, understand, and ask questions. If you couldn't read something or were too slow, you could not study this part.
By solving the problem in more than one way! This should be very achievable in a field like discrete math. First solve the problem by hand, then model the program in something like Mathematica or OR-Tools and see if you can get the same solution.
This would work even better in a lower level maths like Algebra and Calculus. Just use Mathematica's Solve[] function for many problems and you'll know if you were right or wrong.
One can also use this approach in an algorithms class. Write your own naïve program to trivially but reliably solve test cases, then compare your more sophisticated algorithms to these results. Alternatively, use a reference implementation from some other library. For example, compare your own graph algorithm solutions to what Neo4j returns.
This would work even better in a lower level maths like Algebra and Calculus. Just use Mathematica's Solve[] function for many problems and you'll know if you were right or wrong.
One can also use this approach in an algorithms class. Write your own naïve program to trivially but reliably solve test cases, then compare your more sophisticated algorithms to these results. Alternatively, use a reference implementation from some other library. For example, compare your own graph algorithm solutions to what Neo4j returns.
Or save yourself hundreds of hours and find a textbook with solutions.
I think that each may book should at least have all problem solutions at least, and most problem resolutions as well, leaving some room problem to be solved without giving the resolution, for training. Anything short of that can only be used as a reference book by a teacher, because teachers need to confirm that the resolution is indeed complete and right. Without that, as a engineering and economics student (decades ago), my resolutions would often have been incomplete and lack some details and specific cases.
These days chatgpt can fill the gap surprisingly well for many questions.
ChatGPT can help with very simple problems that people have already solved online. That said, typically, you can search for the actual solution online without the ChatGPT's possible hallucinations.
A better use of LLM is to input your reasoning and ask if it is correct, but even then, you can't rely on the output. Probably the best is to ask on the math side of stack overflow and rely on the kindness of a stranger.
A better use of LLM is to input your reasoning and ask if it is correct, but even then, you can't rely on the output. Probably the best is to ask on the math side of stack overflow and rely on the kindness of a stranger.
I wouldn't count on it -- LLMs make lots of errors in reasoning, and errors in solutions are very frustrating to most math students.
Without any solutions or even problems to begin with and without having a teacher by your side, I found that LLMs can be a good-enough learning assistant. Of course, you cannot rely on their answers and they sometimes lead you astray, but what works for me is to:
- throughout the text, use the LLM to ask questions, generate problems (I haven’t tried this yet, so it might not work very well) and give you hints on how to close the gaps in your understanding
- reduce a given problem to the simplest possible case and ask how to solve that (if you want to check if your solution seems plausible) or if it can give you hints on how to approach the problem (when you are stuck)
- vary the problem description to see if different approaches are suggested
- critically ask questions about the (steps to the) solution or any provided hints (does something seem odd or logically inconsistent?)
- other LLMs sometimes give you better answers (or contradict each other), so, if possible, try asking different LLMs the same questions
Having this “conversation” with the LLM where you need to critically check everything it says has the added benefit of being more actively engaged with the material as opposed to simply looking up the solution. It may be a huge waste of time if you’re not careful, but I think if you use it intelligently to guide your own thinking, it can be very helpful.
- throughout the text, use the LLM to ask questions, generate problems (I haven’t tried this yet, so it might not work very well) and give you hints on how to close the gaps in your understanding
- reduce a given problem to the simplest possible case and ask how to solve that (if you want to check if your solution seems plausible) or if it can give you hints on how to approach the problem (when you are stuck)
- vary the problem description to see if different approaches are suggested
- critically ask questions about the (steps to the) solution or any provided hints (does something seem odd or logically inconsistent?)
- other LLMs sometimes give you better answers (or contradict each other), so, if possible, try asking different LLMs the same questions
Having this “conversation” with the LLM where you need to critically check everything it says has the added benefit of being more actively engaged with the material as opposed to simply looking up the solution. It may be a huge waste of time if you’re not careful, but I think if you use it intelligently to guide your own thinking, it can be very helpful.
The HN community might be interested in the XML-based tech used to produce this book, namely https://pretextbook.org/
Sadly the "source on github" links are broken on https://pretextbook.org/examples.html
In fact, I came to the comments to ask. Thank you!
What a lovely resource! Thank you, author.
I just wanted to thank all the authors, especially of textbooks, who put their work online, for free. Their dedication shows, and how. It is largely due to these free (and free-ish) resources that many people -- including autodidacts and those with limited resources -- are able to further their education.
Authors - know that your efforts are very much appreciated!
I just wanted to thank all the authors, especially of textbooks, who put their work online, for free. Their dedication shows, and how. It is largely due to these free (and free-ish) resources that many people -- including autodidacts and those with limited resources -- are able to further their education.
Authors - know that your efforts are very much appreciated!
Bit late to the party, but I can warmly recommend "Discrete mathematics with applications" by Susanna Epp. There are a couple of books with similar titles, but the ones by Epp are amazingly well written. An incredible amount of care and attention to detail went into this textbook, and it shows. Excellent for self study.
The Math Sorcerer did a video on an older edition, which is just a lovely ode to the book, the man is in love. https://www.youtube.com/watch?v=FPr5-X9nZc4
The Math Sorcerer did a video on an older edition, which is just a lovely ode to the book, the man is in love. https://www.youtube.com/watch?v=FPr5-X9nZc4
Like too many discrete math texts, the Characteristic Root Technique for Repeated Roots section does not give a proof of the forumla.
It is a consequence of the form of the characteristic equation: if the double root is r, then expanding out x^2 - 2r + r^2 and matching terms we see that a = 2r and b = -r^2; in other words, the recurrence is
a(n) = 2r a(n-1) - r^2 a(n-2).
c(n) = 2c(n-1) - c(n-2), where c(n) = a(n)/r^n
c(n) - c(n-1) = c(n-1) - c(n-2)
a(n) = c(n) r^n = (x*n + y) r^n.I think because a full proof covering existence and uniqueness will either be really long or require tools from outside the scope of the text. E.g. there's a somewhat concise proof using linear algebra which I'll partially reproduce below. (I like this proof because the equation is derived from first principles rather than starting with an ansatz.)
---
Let x_n be a sequence defined by the recurrence relation:
---
Let x_n be a sequence defined by the recurrence relation:
x_{n+1} = a * x_{n-1} + b * x_n
[x_0] [x_1] [x_2]
[x_1], [x_2], [x_3], ...
[x_1] = [[0 1]] [x_0]
[x_2] [[a b]] [x_1]
y_1 = M * y_0
y_2 = M * y_1
= M * (M * y_0)
= M^2 * y_0
y_n = M^n * y_0
r^2 - br - a = 0
r_1 = (b - c)/2
r_2 = (b + c)/2
c = √(b^2 + 4a)
y_n = S * [[r_1^n 0 ]] * S^(-1) * y_0
[[0 r_2^n]]
This reminded me of something else... I remember contrasting the discrete math course I took (circa 1990) to Knuth's AoCP and how Knuth used generating functions to find the closed form for recursive series (and IIRC didn't even cover any other methods). The course I took didn't touch on generating functions and most other textbooks I read didn't either.
Interesting to see that this book does cover the topic. I guess "discrete math" can be a lot of different things.
Interesting to see that this book does cover the topic. I guess "discrete math" can be a lot of different things.
I wish I even liked my field the way the folks who write these free textbooks love theirs.
Ah, my favorite course in uni. It made me pick both math and ai majors; math for formal verification because I like discrete math so much in my first year.
> A PDF of the book will be made available by August 15th.
On the sidebar:
> PDF coming soon
:(
On the sidebar:
> PDF coming soon
:(
The PDF really is coming soon. I ran into some snags getting it to compile. Should be fixed by Monday
Are you paying for it? If not, you don't have a right to complain.
Of course he has a right to say his opinion. And this doesn't even count as "complaining".
Don't turn this into a general rule:
Payer Patrick pays molester Maverick to maim or intimidate victim Victor.
Is Victor allowed to complain? Or only the person who paid?
Payer Patrick pays molester Maverick to maim or intimidate victim Victor.
Is Victor allowed to complain? Or only the person who paid?
What?
Is discrete maths a good starting point if I was interested in cryptography? Certainly better than analysis right?
Definitely, in fact Cryptography was added on as a trailer to my Discrete Math course.
Yeah it's a building block for understanding number theory well, which is important in cryptography.
One cool thing about math though is that continuous/analysis concepts and discrete concepts interact with each other. There's a fair bit of calculus in e.g. AoCP. At some point number theory as well. Kind of depends on how deep you want to go. You can learn a lot about cryptography without really needing a very strong mathematical base.
Seems pretty cool, especially for being free! I'm taking a discrete math course very soon at UT so this is nice.
I really like the book “A Primer of Discrete Mathematics”[1] by Finkbeiner II and Lindstrom from 1987. It’s a bit old and unfortunately not free but still holds up pretty well and has many good exercises with selected answers.
I will absolutely check out this book though, looks like a more modern approach with interactive exercises and it even is completely free!
[1]: https://archive.org/details/isbn_0716718154