Discrete Structures

# Functions & Sequences

 Last Update: 3 November 2010 Note: or material is highlighted

1. Functions:

1. Diagrams of functions (Rosen, §2.3, Fig. 5, p. 139)

2. Rapaport, William J. (2007), "What Is Computation?"

• Describes what a function is, and relates it to the notion of computation.

3. O'Connor, J.J.; & Robertson, E.F. (2005), "The Function Concept"

• A brief history of the concept of "function"

4. Does a function in mathematics change anything?

2. Sequences:

1. Computational Learning Theory

1. The usual SAT or GRE problem of figuring out the next term in a sequence is a computationally difficult problem that forms the basis of computational learning theory (CoLT).

• Besides the link above (to former UB Prof. John Case's webpage on CoLT, see also "What is COLT?" (when you click on this link, scroll down to "What is COLT?").

Here are some examples of why this is difficult:

2. "… surely, at least the mathematical questions on IQ tests are objective. This mistakes the issue. If asked to continue the sequence ‘1, 1, 2, 3, 5’, many people would recognize the Fibonacci sequence and say ‘8’. But there are infinitely many other sequences where the next number is 7 (for example, ‘pick the largest prime number less than or equal to the sum of the previous two numbers’), or even 11 (‘pick the smallest prime number greater than or equal to the sum of the previous two numbers’). What's tested by [such sequences] is not how well you can find patterns, but how well you can find the patterns [that the author of the question] liked." (p. 247.)

3. "Suppose that some natural process yields the sequence 1,2,3&hellip How does it continue? Of course, we have far too little data to know. It might oscillate (1,2,3,2,1,2,3,2,1…), become ‘stuck’ (1,2,3,3,3,3&hellip), exhibit a Fibonacci structure (1,2,3,5,8…), and any of an infinity of more or less plausible alternatives. This indeterminacy makes the problem of […]induction of structure from the natural world difficult, although not necessarily hopelessly so, in the light of recent developments in statistics and machine learning […]. But consider the parallel problem of [cultural] learning—we need not guess the ‘true’ continuation of the sequence. We only have to coordinate our predictions with those of other people in the community. This problem is very much easier. From a psychologocial point of view, the overwhelmingly natural continuation of the sequence is ‘…4,5,6….’"

4. For more on this topic, see:

2. The On-Line Encyclopedia of Integer Sequences

• What rule generates this sequence?

• 1, 11, 111, 15, 5, 51, 511, 5111, 110, 10, 101, 1011, 10111, 1015, 105, ...

For the answer, enter that sequence in the above website's search box!

3. "Sequences and Summations: Further Information"

4. Rapaport, William J. (1974), "Paper Folding and Convergent Sequences", Mathematics Teacher 67 (May): 453-457.

• Discusses an interesting sequence that can be constructed by folding a strip of paper and that converges to a surprising number.
• (My very first publication, too! :-)

5. Felleisen, Matthias; & Krishnamurthi, Shriram (2009), "Why Computer Science Doesn't Matter", Communications of the ACM 52(7) (July): 37–40.

• §"How Would This Work?", pp. 38–39, contains an interesting example of a graphical sequence.

6. How to Add 5 Consecutive Numbers Quickly

Copyright © 2009–2010 by William J. Rapaport (rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/F09/functions.html-20101103