Why does undergraduate discrete math require calculus? - MathOverflow

Why does undergraduate discrete math require calculus?

2010-06-04T18:32:18Z

Often undergraduate discrete math classes in the US have a calculus prerequisite.

Here is the description of the discrete math course from my undergrad:

A general introduction to basic mathematical terminology and the techniques of abstract mathematics in the context of discrete mathematics. Topics introduced are mathematical reasoning, Boolean connectives, deduction, mathematical induction, sets, functions and relations, algorithms, graphs, combinatorial reasoning.

What about this course suggests calculus skills would be helpful?

Is passing calculus merely a signal that a student is ready for discrete math?

Why isn't discrete math offered to freshmen — or high school students — who often lack a calculus background?

Answer by coudy for Why does undergraduate discrete math require calculus?

2010-06-04T18:45:38Z

I see three reasons.

Generating functions is an example of tools used in discrete mathematics. Calculus definitely helps working with them.

Binomial coefficients arise frequently in discrete math. Many formulas about these coefficients can be handled by calculus.

Also, even if you are interested only on what happens for finite sets of size n, probably you will want to let n goes to infinity at some point, and then continuous laws, integrals and the like will appear naturally.

Still I think that it is possible to teach a beginner course in discrete mathematics which does not rely on calculus.

Answer by Andrey Rekalo for Why does undergraduate discrete math require calculus?

2010-06-04T19:11:35Z

Sometimes it's difficult even to write an answer to a discrete math problem without an integral or two.

Example. The number of integer lattice points that satisfy the conditions $$-n\leq x,y,z\leq n,\quad -s\leq x+y+z\leq s$$ for some $n$, $s\in\mathbb N$, is equal to $$\frac{1}{2\pi}\int\limits_{-\pi}^{\pi}\left(\frac{\sin \frac{2n+1}{2}t}{\sin\frac {t}{2}}\right)^3\frac{\sin \frac{2s+1}{2}t}{\sin \frac{t}{2}} dt. $$

Answer by engelbrekt for Why does undergraduate discrete math require calculus?

2010-06-04T19:15:12Z

Where I work, the first-semester science students are offered two mathematics courses: One-variable calculus and introductory discrete mathematics. Obviously the emphasis in the latter course cannot be on solving counting problems in terms of elementary functions, since calculus is the main tool for handling these. The course contains combinatorics, graph theory and number theory up to congruences. Calculus is not a prerequisite.

Answer by Alexander Woo for Why does undergraduate discrete math require calculus?

2010-06-04T20:09:16Z

A significant portion (my observation was about 20-30% at Berkeley, which means it must approach 100% at some schools) of first year students in the US do not understand multiplication. They do understand how to calculate $38 \times 6$, but they don't intuitively understand that if you have $m$ rows of trees and $n$ trees in each row, you have $m\times n$ trees. These students had elementary school teachers who learned mathematics purely by rote, and therefore teach mathematics purely by rote. Because the students are very intelligent and good at pattern matching and at memorizing large numbers of distinct arcane rules (instead of the few unifying concepts they were never taught because their teachers were never taught them either), they have done well at multiple-choice tests.

These students are going to struggle in any calculus course or any discrete math course. However, it is easier to have them all in one place so that one instructor can try to help all of them simultaneously. For historical reasons, this place has been the calculus course.

Answer by Chris Phan for Why does undergraduate discrete math require calculus?

2010-06-04T20:33:14Z

Perhaps it's done to ensure a certain level of mathematical maturity. For example, here is what one author writes in the preface to his discrete mathematics text:

This book has been written for a sophomore-level course in Discrete Mathematics. [. . .] Students are assumed to have completed a semester of college-level calculus. This assumption is primarily about the level of the mathematical maturity of the readers. The material in a calculus course will not often be used in the text.

(Eric Gossett, Discrete Mathematics with Proof, 2nd ed., John Wiley and Sons, 2009)

Answer by hypercube for Why does undergraduate discrete math require calculus?

2010-06-04T21:19:49Z

Although calculus is not frequently used in discrete mathematics it is nice to know that the students have had at least some exposure to sets and functions. I am teaching discrete this summer and find myself saying "you have seen this in calculus" when talking about several fundamental concepts.

When doing proofs in a calculus course I usually try to point out the fundamental concepts from the course that are needed and in a discrete course the actual process of how do do a proof is studied more closely. Again it is nice to know that at least the students have seen proofs before and we can build on this exposure.

Answer by Victor Protsak for Why does undergraduate discrete math require calculus?

2010-06-04T22:01:36Z

In the context of college students, I agree with Alexander Woo's explanation. By the way, the best and the brightest often place out of calculus (that's the case at Yale, and I imagine it's not that much different at Berkeley), so the percentages of weak students at best schools aren't as dire as you might think.

Concerning the last question,

"Why isn't discrete mathematics offered to high school students without calculus background?"

Not only is that possible, but it had been the norm in the past within the "New Math" curriculum, when everyone had to learn about sets and functions in high school. This ended in a PR disaster and a huge backlash against mathematics, because generations of students were lost and got turned off by mathematics for life; some of them later became politicians who decide on our funding. Consequently, it was abandoned. (Apparently, calculus in HS was introduced as a part of the same package and survived.)

I'd be interested to know if there are any high school – college partnerships that offer discrete mathematics to H.S. students with strong analytical skills, and how do they handle the prerequisites question.

Answer by Noah Snyder for Why does undergraduate discrete math require calculus?

2010-06-05T04:29:34Z

In the context of very bright high school students with strong mathematics backgrounds, it is typical to teach discrete math to students without requiring calculus as a prerequisite. In particular, this is the norm both at the Ross program (where 2nd year students often had a combinatorics class) and at Mathcamp (where many discrete math classes are often taught without calculus as a prerequisite). Both summer programs avoid teaching calculus because it messes up highschool students who are going to be stuck taking calculus whether they already know it or not.

In particular, it's quite possible to teach formal differentiation and integration of power series in order to do generating functions without discussing traditional differentation or limits. In fact, the Ross problem sets had a problem set developing the basics of calculus for polynomials (linearity, Leibniz rule, etc.) without ever discussing limits. I'd already learned calculus at that point, but not all the students had. And the students who didn't know calculus didn't have too much of a difficulty with that problem set. It's certainly easier than proving that the group of units modulo p is cyclic.

So the reason for requiring such a prerequisite for a college course is not that it's actually a logical prerequisite, but instead for sociological reasons along the lines of Alex's answer.

Answer by Gerry Myerson for Why does undergraduate discrete math require calculus?

2010-06-05T13:33:12Z

When I was at Buffalo 30 years ago, Tony Ralston advocated teaching discrete math instead of calculus to 1st year students. I taught it out of some notes he had prepared, and thought the students found it harder than calculus. It was easier to relate calculus topics to things they already knew about than it was to do that for the topics in his notes.

I'm pretty sure those notes became a textbook, so you can probably get a copy and see one man's idea of what should/could be taught to students before calculus.

Answer by J W for Why does undergraduate discrete math require calculus?

2010-08-31T16:44:40Z

Today I came across the following article that might be of interest: Has Our Curriculum Become Math-Phobic? by Keleman et al. The authors address mathematics in the computer science curriculum and advocate the early introduction of discrete mathematics.

Answer by kcrisman for Why does undergraduate discrete math require calculus?

2011-01-13T02:33:19Z

This has been dormant for a while, but it's worth pointing out the ACM recommendations, which essentially say what J W says - but I don't have enough rep to vote up that answer or comment on it, so I provide the link here for those searching for info. The ACM also recommended calculus in this set of recs, whereas the update is more about the core CS curriculum. It's also worth mentioning that the ACM is focused more on "sound reasoning", not "formal symbolic proof", in its guidelines. That doesn't necessarily mean less mathematical, from what I can tell.