For each of the following sequences find a simple function a(n) such that the sequence is a(1), a(2), a(3),..Some students found this problem difficult. Looking back at it they may be right- the pattern is not obvious for students at that level who do not know what to look for. Some noted correctly that the term simple function was not defined in class. I meant a function that does not involving summations or recurrences, though I do not think that quite captures the notion. For example, if a student wrote a poly that interpolated the values given that is not that I wanted. I could ask for the function with the least Kolmogorov complexity to describe but that's not quite right for this sophomore class where they struggle to learn induction.
a) 10, -17, 24, -31, 38, -45, 52, ...
b) -1, 1, 5, 13, 29, 61, 125, ...
c) 6, 9, 14, 21, 30, 41, 54, ...
(For the answer see here)
One of them, in earnest, emailed me this Wikipedia entry on simple functions which defines them as a linear combination of indicator functions of measurable sets. Hmmm- not quite what I had in mind for this class. The student wanted to know if he could use it. I told him no; however, in retrospect, I wonder what he would have come up with.
I had not known that the term simple function had a formal definition. Usually in a class there are concepts that are well enough defined within the class though not quite formal. With Wikipedia (and other web sources) it may be harder to have this kind of classroom-language since terms may have a formal definition that you didn't know.
When you said simple function, the first thing I thought of was a function with finite range, just like the one you described. Seems like sequences you could describe with a simple function would be kind of boring!
ReplyDeleteI wonder what is the point of asking such questions to the students? And in particular, what is the point of asking for a simple function (whatever it means) to interpolate the values and not accepting that the students gives an interpolating polynomial. It seems much interesting to me for a student to compute a interpolating polynomial than to guess 2^n-3.
ReplyDeleteI shall say that I never taught a sophomore discrete math course, so I never really thought to what should be taught in such class and how. I was just quite surprised that you asked such questions! But I'd really like to understand the (good, for sure!) reasons you did it.
Bill, I have to disagree with you when you point to "the" answer, since there are many --in fact infinitely many-- answers to each question, and even if only one of them counts as "simple", we still need that definition to check that it is, indeed, simple!
ReplyDeleteThis reminds me of some questions in the PSU (our national equivalent to SAT), question of the kind: "What is the next number in the sequence 2, 4, 6,...?". It is inherently a mistake to consider the sequence as being uniquely identified. One student might think of even numbers and answer 8, while other might think of "odd prime numbers minus 1" and answer 10, but it would probably be "wrong" (officially, at least).
All of them can be looked up in OEIS. Meaningless exercise.
ReplyDeleteEven if this kind of questions made sense from ML point of view, the size of data set is too small. Kolmogorov complexity neither makes sense, it completely depends on the the K function you have in mind. I strongly dislike these kind of question, you are essentially asking students to guess what you have in mind. Do you think it is going to help them in predicting the stock market or something? What is the point of these questions?
ReplyDeleteAnon- We were going to be induction and one of the things
ReplyDeletethat you prove by induction is
given a recurrence for sequence (e.g., a(0)=1, a(i)=2a(i-1)) find an expression in closed form. I like
to have the students caluclate a few of the values and say
thinks like `OH, that looks like 2^n !' and then prove it.
This excercise was practice in that, though we gave them
the numbers directly.
More generally, it comes up in math that you see a sequence
(or something more complicated) and need to speculate
or guess on what it might be.
Janorma- YES these problems need not have unique answers.
Thats why I gave the many terms of the sequence
and asked for a simple expression. Part of my
point of the post is that a class develops its
own terminology and understanding that might not be
well understood outside of the class. It was my
hope that SIMPLE FUNCTION would be one of them.
Out of curiosity, at what point would you expect that a student of math or CS would know what to look for in these sequences?
ReplyDeleteI find it amazing when people complain that such problems do not have a unique solution. It seems like everything in life should have a unique solution...
ReplyDeleteNoticing patterns is important because most people work by observing, conjecturing and proving. Of course, we may try proving first more complicated, general patterns. Good luck in such case.
Anon-OES- My hope was to give sequences simple enough so that they wouldn't need OES.
ReplyDeleteAnon-Kolm- I didn't really expect to be able to define this using Kolm complexity.
Anon-Curious-what-point- Depends on the complexity of the sequence. The sequence 1,2,4,8,16 (which I WOULD NOT
trick them on by saying its something else) I would
expect they would be able to figure out in HS. The problem I gave them I HAD THOUGHT they could do before
learning induction, but upon giving it some of my
VERY GOOD students could not do it (and not becuase it was ill defined) so I would now say a good student
AFTER a course in discrete math should be able to do it.
Anon-OES again- You raise an interesting question.
Since computers can do certain things do we need to
ask the students to do them? Should students not be
required to know what 7*8 is since they have calculators? Should students not be able to guess
what 1,3,5,7,9,... is because they have OES?
Should students no longer be able to derive that
sum_{i=1}^n i = n(n+1)/2 because they have
Wolfram Alpha? For the examples I picked I think
they are too easy to say THE STUDENTS NEED NOT KNOW IT,
but (1) you may respectfully disagree, and
(2) there IS some cutoff where the students really shouldn't need to know stuff, but not sure where it is.
I would say simple functions are those which can be understood by a pupil in 10th grade in Bavaria, Germany (sin(x), cos(x), tan(x), a^x, log_n(x), abs(x), all polynomial functions, recursive functions, and any possible chaining of these (in R)). So all n-ary functions with n >= 2 are not simple, ceil(x), floor(x), the ackermann function, ...
ReplyDeleteIn this context I thought you might want to prohibit the excessive use of defining the function (sorry for my bad English, I think I'll make an example):
a(1) = 10
a(2) = -17
a(3) = 24
a(4) = -31
a(5) = 38
a(6) = -45
a(n) = 52, n >= 7
I just want to try this for myself:
a(1), a(2), a(3),..
a) 10, -17, 24, -31, 38, -45, 52, ...
.....-27 +41 -55 +69 -83 +97
...... +65 -96 +124 -152 +180
... seems not to work
lets try it with the absolute value as the sign seems to alternate:
a) 10, -17, 24, -31, 38, -45, 52, ...
..... +7 +7 +7 +7 +7 +7
=> f(x) = (3+7*x)*(-1)^(1+x)
b) -1, 1, 5, 13, 29, 61, 125, ...
.....+2 +4 +8 +16 +32 +64
=> recursive: g(1) = -1; g(x) = g(x-1) + 2^(x-1)
=> non-recursive: g(x) = 2^x - 3
c) 6, 9, 14, 21, 30, 41, 54, ...
....+3 +5 +7 +9 +11 +13
..... +2 +2 +2 +2 +2
=> recursive: h(1) = 6; h(x) = h(x-1) + (2*x-1)
=> non-recursive: h(x) = 6 + (2^x - 1) = 5 + 2^x
lets see if I was correct:
a) correct
b) correct
c) correct
juhu :D
By the way, the method I demonstrated for finding the sequence can be used for finding a reasonable sucessor for every sequence. Sometimes, like my first try for a), you can be quite sure that the sucessor you might get will not be the on that the questioner wants to hear, but it is never the less a reasonable sucessor. Has this method a name? I created it by myself, but I guess I'm not the first one who uses it.
I hate questions like this.
ReplyDeleteA(n) = [10, -17, 24, -31, 38, -45, 52][n mod 7]
B(n) = [-1, 1, 5, 13, 29, 61, 125][n mod 7]
C(n) = [6, 9, 14, 21, 30, 41, 54][n mod 7]
Yes, I teach students to solve recurrences, too. But I also teach them that's it's dangerous to generalize from small examples; every "What's next in this sequence?" question has an infinite number of answers.
Recurrences give strong hints about their solutions; they certainly contain more information that their first few initial values. (Look at f(n) = 2f(n-1). Do you know of any sequences of integers that double in every iteration BY DEFINITION?)
Moreover, most simple recurrences (meaning almost all recurrences that show up in an undergraduate CS curriculum) can be solved directly (at least up to constant factors) using fairly simple techniques. Yeah, it's important to fall back on guessing when you have no alternative, but that circumstance is really quite rare.
In this context, I ask students to find a "closed-form expression" which is exactly that, a function without summation or recurrences but at least they have seen that before and have some methods to guide them. I agree that's a question of terminology. That will make a great entry in my glossary puzzle for Discrete Math!
ReplyDeleteI've long said … in mathematics, simple and normal things aren't.
ReplyDeleteBad type of question, in my opinion. The one redeeming quality of math (as non-mathematicians see it) is its precision and exactness and unambiguity. That's completely missing in these questions. For the purpose of teaching them pattern-finding, it'd be better to teach them how to use the OEIS.
ReplyDeleteThe meta-question is: what exactly is this question trying to teach them? (Or, if you prefer, what is it trying to demonstrate that they have learned?) Random guessing? Brute-force search through some canonical list of "simple" functions? Web searching for the answer?
ReplyDeleteYou said that your goal was to teach them how to prove (using induction) that some given recurrence has some given closed form. So why not just give them a question like that?
I don't think this kind of question is bad, or misleading, or anything of the sort. I remember being fascinated by this sort of thing in high school. I wish more students were confronted with this kind of question there. But better in sophomore year than never. Of course it's true that there is never a unique answer. And that in itself is something that students at that level can easily understand, and --- even more -- learn to appreciate. And in any case, there are are two things this kind of question leads to:
ReplyDeletea) Kolmogorov complexity --- what's the "least complicated" way of describing the sequence? OK, I'm mainly kidding here. This is way too sophisticated for students at this level to get a good grasp on. But the question can be posed, at any rate, and I'm sure many of them might at least understand that there *is* a question there.
b) It does, as you have intended, lead directly to the use of mathematical induction. That's good in itself.
I have found, by the way, that many students believe that mathematical induction consists in proving the correctness of formulas. That I suppose is a problem, not so much with this kind of question, but with the fact that it may be the *only* way in which mathematical induction is presented. So many elementary graph-theoretical properties are inductive in nature --- and they're important in even reasonably low-level computer science -- that students need to be exposed to them as early as possible. But I think it's undoubtedly true that graphs for some reason seem to be more sophisticated than the natural numbers for most students -- at least, until they find out how unintuitive and terminally complex infinite sets like the natural numbers really are.
Is there a way to define the notion of a "simple function" without using the notion of a function in the definition either explicitly (indicator functions) or implicitly (sets)?
ReplyDeleteThe word verification for the previous post was "musses".
ReplyDeleteMartin Thoma,
ReplyDeletelast line should probably read 5+x^2 instead of 5+2^x