Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

Math Discovery Examples

Learning Cycle: Thread

Thread* T) Extend the domain F) Continuity R) Self-superimposed sequence These three frames are the cycle of the scientific method: take a stand (hypothesize), follow through (experiment), reflect (conclude). I imagine that they link B1, B2, B3, B4 with C1, C2, C3, C4 to weave all manner of mathematical ideas, notions, problems, objects.

Extend the Domain* Consider a constraint such as (2**X)(2**Y) = 2**(X+Y). It may make sense in one domain, such as integers X,Y > 2. If we hold true to the constraint, then we can extend the domain to see what it implies as to how 2**X must be defined for X=1,0,-1,... We can then think of the constraint (2**X)(2**Y) = 2**(X+Y) as stitching together unrelated domains. Such stitching I think allows us, in differential geometry, to stitch together open neighborhoods and thus define continuity for shapes like the torus. 23

• Calculate preliminary examples by hand or with a computer, thus extending the domain by them. For example, in looking for counterexamples, or building evidence for theorems about the relationships between the primes.
• Apply calculus ideas to a discrete problem* For any sequence of real numbers A=(a1,a2,...) define delta-A to be the sequence (a2-a1, a3-a2, a4-a3,...) whose nth terms is a_n+1 - a_n. Suppose that all of the terms of the sequence delta-(delta-A) are 1, and that a19=a94=0. Find a1. Even though this is not a calculus problem - the variables are discrete, so notions of limit make no sense - we can apply calculus-style ideas. Think of A as a function on the subscript n. The delta operation is reminiscent of differentiation; thus the equation delta-(delta-A) = (1,1,1...) suggests the differential equation d2A/dn2 = 1. Solving this (pretending that it makes sense) yields a quadratic function for n. None of this was "correct", yet it inspires us to try guessing that an is a quadratic function of n. And this guess turns out to be correct! pg.313 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2249
• Appropriate new ideas* ...cultivating a confident attitude, so that when you see a beautiful solution, you no longer think, "I could never have done that", but instead think, "Nice idea! It's similar to ones I've had. Let's put it to work!" Learn to shamelessly appropriate new ideas and make them your own. There's nothing wrong with that; the ideas are not patented. If they are beautiful ideas, you should excitedly master them and use them as often as you can, and try to stretch them to the limit by applying them in novel ways. pg.20, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1419
• Complete set of solutions* Given any diophantine equation [an equation whose variables assume only integer values] ... Can we find all solutions? Once one solution is found, we try to understand how we can generate more solutions. It is sometimes quite tricky to prove that the solutions found are the complete set. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2224
• Define a Function* Show, without multipying out, that (b-c)/a + (c-a)/b + (a-b)/c = (a-b)(b-c)(a-c)/abc. Even though it is easy to multiply out, let us try to find a more elegant approach. Notice how the right-hand side factors. We can deduce this factorization by defining f(x) = (b-c)/x + (c-x)/b + (x-b)/c. Notice that f(b) = f(c) = 0. By the factor theorem, if we write f(x) as a quotient of polynomials f(x) = P(x)/xbc, then P(x) must have x-b and x-c as factors. ... By symmetry, we could also define the function ... pg.167 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2177
• Eulerian mathematics* In the last few pages, we have been deliberately cavalier about rigor, partly because the technical issues involved are quite difficult, but mostly because we feel that too much attention to rigor and technical issues can inhibit creative thinking, especially at two times: The early stages of any investigation.; The early stages of any person's mathematical education. We certainly don't mean that rigor is evil, but we do wish to stress that lack of rigor is not the same as nonsense. A fuzzy, yet inspired idea may eventually produce a rigorous proof; and sometimes a rigorous proof completely obscures the essence of an argument. There is, of course, a fine line between a brilliant, non-rigorous argument and poorly thought-out silliness. To make our point, we will give a few examples of "Eulerian mathematics", which we define as non-rigorous reasoning which may even (in some sense) be incorrect, yet which leads to an interesting mathematical truth. We name it in honor of the 18th-century Swiss mathematician Leonard Euler, who was a pioneer of graph theory and generatingfunctionology, among other things. Euler's arguments were not always rigorous or correct by modern standards, but many of his ideas were incredibly fertile and illuminating. Most of Euler's "Eulerian" proofs are notable for their clever algebraric manipulations... Sometimes a very simple yet "wrong" idea can help solve a problem. ... They are excellent illustrations of the "bend the rules" strategy pg.312 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2248
• Existence of solutions* Given any diophantine equation [an equation whose variables assume only integer values] ... Do there exist solutions? Sometimes you cannot actually solve the equation, but you can show that at least one solution exists. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2222
• Make conjectures LCM technique 2 of 5. Our conjecture, by definition, should hold true for some cases. We thus consider how to extend the domain for which it holds.
• Experimentation* When it comes to strategy, combinatorial problems are no different from other mathematical problems. The basic principles of wishful thinking, penultimate step, make it easier, etc. are all helpful investigative aids. In particular, careful experimentation with small numbers is often a crucial step. For example, many problems succumb to a three-step attack: experimentation, conjecture, proof by induction. pg.212 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2204
• Generalizing the scope of a problem* The define a function tool ... is part of a larger idea, the strategy of generalizing the scope of a problem before attacking it. pg. 98, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1642
• Guess the limit* Somehow guess the limit L, and then show that the ai get arbitrarily close to L. pg.285 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2232
• Inequalities* I think inequalities become relevant when we patch together different solution spaces. Inequalities are important because many mathematical investigations involve estimation, optimizations, best-case and worst-case scenarios, limits, etc. Equalities are nice, but are really quite rare in the "real world" of mathematics. ... Of the many ways of proving inequalities, the simplest is to perform operations that create logically equivalent but simpler inequalities. More sophisticated variants include a little massage, as well. pg.189-191 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2189
• Nonexistence of solutions* Given any diophantine equation [an equation whose variables assume only integer values] ... Are there no solutions? Quite frequently, this is the first question to ask. As with argument by contradiction, it is sometimes rather easy to prove that an equation has no solutions. It is always worth spending some time on this question when you begin your investigation. pg.264 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2223
• Substitute Convenient Values* If the polynomial P(x) is divided by x-a the remainder will be P(a). ... To see why the Remainder Theorem is true in general, divide the polynomial P(x) by x-a, getting Q(x) with remainder r. Using the division algorithm, we write P(x) = Q(x)(x-a) + r. The above equation is an identity; i.e., it is true for all values of x. Therefore we are free to substitute in the most convenient value of x, namely x=a. This yields P(a) = r, as desired. pg.181 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2186
• Lie algebra (infinitesimal) vs. Lie group (broader domain).
• Kan extension - extending the domain - every concept is a Kan

Continuity* As in Polya's discussion of Descartes' universal method, we can apply continuity to consider the implications of a constraint or an equation. Polya asks about an iron ball floating in mercury, if we pour water on it, will the ball sink down or float up or stay the same? He answers this by first imagining that the water has no specific gravity (like a vacuum) and then increasing it continuously until it approaches and surpasses that of iron. Varying the variable is putting the constraint to the test, presuming that there is a solution point, just as we do and can in physical reality. At what points will the model break or hold? Continuity is the thread that we sew. 24

• In the data, look for patterns that recur or look for tendencies, how things are proceeding. Critical points help to define such patterns (where they start and end) and such tendencies (where they start and where they change qualitatively).
• Setting a function or its first derivative or second derivative to zero, and so on, establishes critical points (which can also be minimums and maximums in analytic problem solving).
• Continuity* Informally, a function is continuous if it is possible to draw its graph without lifting the pencil. Of the many equivalent formal definitions, the following one is the easiest to use. Let f: D -> R and let a be an element of D. We say that f is continuous at a if the limit as n approaches infinity of f(x_n) = f(a) for all sequences (x_n) in D with limit a. ... Continuity is a condition that you probably take for granted. This is because virtually every function you have encountered (certainly most that can be written with a simple formula) are continuous. ... Consequently, we will concentrate on the many good properties that continuous functions possess. Here are two extremely useful ones. Intermediate-Value Theorem. If f is continuous on the closed interval [a,b], then f assumes all values between f(a) and f(b). ... Extreme-Value Theorem. If f is continuous on the closed interval [a,b], then f attains minimum and maximum values on this interval. ... The extreme-value theorem seems almost without content, but examine the hypothesis carefully. If the domain is not a closed interval, it may not be true. pg.288-289 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2238
• Intermediate-Value Theorem* If f is continuous on the closed interval [a,b], then f assumes all values between f(a) and f(b). ... the IVT, while "obvious"... has many practical applications. ... Let f:[0,1]->[0,1] be continuous. Prove that f has a fixed point; i.e., there exists x in [0,1] such that f(x) = x. ... Let g(x) = f(x)-x. Note that g is continuous and that g(0) = f(0) >=0 and g(1) = f(1)-1<=0. By the IVT, there exists u in [0,1] such that g(u) = 0. But this implies f(u)=u. pg.288-289 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2239
• Interpret dynamically* To understand what a moving curtain is, we shall explore, in some detail, the most important idea of elementary calculus. ... What is the fundamental theorem of calculus (FTC), what does it mean, and why is it true? ... We start with the very useful define a function tool .. Let g(t) = integral from a to to of f(x) with regard to x. We choose the variable t on purpose, to make it easy to visualize g(t) as a function of time. As t increases from a, the function g(t) is computing the area of a "moving curtain" ... Notice that g(a) = 0. ... Differentiation is not just about tangent lines - it has a dynamic interpretation as instantaneous rate of change. Thus g'(t) is equal to the rate of change of the area of the curtain at time t. ... The area grows fast when the leading edge of the curtain is tall, and it grows slowly when the leading edge is short. It makes intuitive sense that g'(t) = f(t) since in a small interval of time delta-t, the curtain's area will grow by approximately f(t)delta-t. ... The crux move was to interpret the definite integral dynamically, and then observe the intuitive relationship between the speed that the area changes and the height of the curtain. This classic argument illustrates the critical importance of knowing as many possible alternate interpretations of both differentiation and integration. Note that the variable "t" is understood here as time and that is part of the necessary implicit context for understanding. pg.282-284 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2230
• Stretching things* Three women check into a motel room which advertises a rate of $27 per night. They each give $10 to the porter, and ask her to bring back 3 dollar bills. The porter returns to the desk, where she learns that the room is actually only $25 per night. She gives $25 to the motel desk clerk, returns to the room, and gives the guests back each one dollar, deciding not to tell them about the actual rate. Thus the porter has pocketed $2, while each guest spent 10-1 = $9, a total of 2 + 3 x 9 = $29. What happened to the other dollar? ... try stretching things a bit: what if the actual room rate had been $0? Then the porter would pocket $27 and the guests would spend $27, which adds up to $54! pg. 22, 102, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1649
• Topologically equivalent* ... the original problem was almost immediately equivalent to the modified easier version. That happened for a mathematical reason: the problem was a "topological" one. This "trick" of mutating a diagram into a "topologically equivalent" one is well worth remembering. pg.19, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1418
• Lautaro Vergaro It was early in 1696 that Johann Bernoulli solved the problem of finding the curve of quickest descent; he showed that the brachistochrone was a cycloid. Johann Bernoulli solved the problem via a brilliant thought experiment, by considering a non-uniform optical medium which becomes increasingly less dense from top to bottom and using the law of refraction and Fermat's principle.

Self-superimposed sequence* We can formulate what we have learned in general. We do this by considering a local constraint on values as a recurrence relation (on values a1, a2, ..., aN) and then superimposing the resulting sequence upon itself, as with a generating function, yielding a global relationship of the function with itself. If the model holds, then it can be tested further. This automata is the hand that makes the stitch. (Recurrence relation as an automata, auto-associative memory of neurons as in Jeff Hawkins' "On Intelligence", generating function, telescoping tool, shift operator) 74

• Mod out by patterns observed and see what is left. For example, mod out by the kernel of a map.
• Arithmetic Mean* An arithmetic sequence is a sequence of consecutive terms with a constant difference ... a, a+d, a+2d, ... An arithmetic series is a sum of an arithmetic sequence. The sum of an arithmetic sequence is a simple application of the Gaussian pairing tool ... Upon adding, we immediately deduce that S = n((A+L)/2), the intuitively reasonable fact that the sum is equal to the average value of the terms multiplied by the number of terms ... another term for "average" is arithmetic mean. pg.172-173 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2179
• Auto associative memory of neurons* Jeff Hawkins discusses auto-associative memory of neurons in his book "On Intelligence", where cortical columns use time-delay to relate patterns to themselves. 79
• Be on the lookout for new ideas* Always be on the lookout for new ideas. Each new problem that you encounter should be analyzed for its "novel idea" content. pg.20, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1420
• Be wary interchanging a “limit of a limit"* ...something disturbing happened. Each an(x) is continuous (in fact, differentiable), yet the infinite sum of these functions is discontinuous. This example warns us that infinite series of functions cannot be treated like finite series. There are plenty of other "pathologies", for example, a function f(x) defined to be the infinite sum of fi(x), yet f'(x) is not equal to the sum of the fi'(x). The basic reason behind these troubles is the fact that properties like continuity, differentiation, etc. involve taking limits, as does finding the sum of a series. It is not always the case that a "limit of a limit" is unchanged when you interchange the order. Luckily, there is one key property that prevents most of these pathologies: uniform convergence, which is defined in the same spirit as uniform continuity ... We say that the sequence of functions (fn(x)) converge uniformly to f(x) if the "N response" to the "epsilon challenge" is independent of x. pg.309 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2246
• Catalyst* Sometimes telescoping won't work with what you start with, but the introduction of a single new term will instantly transform the problem. We call this the catalyst tool. ... Simplify the product (1 + 1/a)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)). Call the product P and consider what happens when we multiply P by 1 - 1/a. The "catalyst" is the simple difference of two squares formula (x-y)(x+y) = x**2 - y**2. (1 - 1/a)P = (1 - 1/a)(1 + 1/a)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)) = (1 - 1/a**2)(1 + 1/a**2)(1 + 1/a**4) ... (1 + 1/a**(2**100)) etc. = (1 - 1/a**201). pg.175 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2181
• Define a function* The define a function tool ... is part of a larger idea, the strategy of generalizing the scope of a problem before attacking it. pg. 98, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1641
• Generating functions* The crossover tactic of generating functions owes its power to two simple facts.
  • When you multiply x**m by x**n, you get x**(m+n).
  • "Local" knowledge about the coefficients of a polynomial or power series f(x) often provides "global" knowledge about the behavior of f(x), and vice versa.

The first fact is trivial, but it is the technical "motor" that makes things happen, for it relates the addition of numbers and the multiplication of polynomials. The second fact is deeper ... Given a (possibly infinite) sequence a0, a1, a2, ..., its generating function is a0 + a1 x + a2 x**2 + ... In general, we don't worry too much about convergence issues with generating functions. As long as the series converges for some values, we can usually get by ... The term "generatingfunctionology" was coined by Herbert Wilf, in his book of the same name. We urge the reader to at least browse through this beautifully written textbook, which among its many other charms, has the most poetic opening sentence we've ever read (in a math book). pg.143-144, 149 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2164

• Geometric series tool* Let 1=a0=a1=a2=... Then the corresponding generating function is just 1 + x + x**2 + x**3 + ... This is an infinite geometric series which converges to 1/(1-x), provided that |x|<1 pg.144, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2165
• Power series* A power series is a special case of a series of functions, namely one where each term has the form an(x-c)**n. ... What makes power series so useful is that they converge uniformly so long as you contract the radius of convergence a bit. ... Thus, once you are in possession of a uniformly convergent power series, you can abuse it quite a bit without fear of mathematical repercussions. You can differentiate or integrate term by term, multiply it by other well-behaving power series, etc. and be sure that what you get will behave as you think it should. ... Not only are they easy to manipulate, but they provide "ideal" information about the way the function grows. pg.311-312 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2247
• Recurrence* Many problems involving the natural numbers require finding a formula or algorithm that is true for all natural numbers n. If we are lucky, a little experimenting suggests the general formula, and we then try to prove our conjecture. But sometimes the problem can be so complicated that at first it is difficult to "globally" comprehend it. The general formula may not be at all apparent. In this case it is still possible to gain insight by focusing on the "local" solution, the transition from n=1 to n=2, and then, more generally, the transition from n to n+1. ... In how many ways can an nx2 rectangle be tiled by 1x2 dominos? ... we have the recurrence formula t_n+1 = t_n + t_n-1 for n=2, 3,... Have we solved the problem? Yes and no. [The formula], plus the boundary values t_1 = 1, t_2 = 2, completely determine t_n for any value of n, and we have a simple algorithm for computing the values: just start at the beginning and apply the recurrence formula! ... These values are precisely the Fibonacci numbers... So the problem is "solved", in that we have recognized that the tiling numbers are just Fibonacci numbers. Of course you may argue that the problem is not completely solved, as we do not have a "simple" formula for t_n (or f_n). ... While it is nice to have a "simple" formula that generates the Fibonacci sequence, knowing the recurrence formula is almost as good, and sometimes it is impossible or extremely difficult to get a "closed-form" solution to a recurrence. ... Compute the number of different triangulations of a convex n-gon ... t_n = sum over u+v = n+1 of t_u t_v ... known as the Catalan numbers ... Recurrence formulas ... may seem rather complicated, but they are really straightforward applications of standard computing ideas (partitioning and simple encoding). Algebraically, the sum should remind you of the rule for multiplying polynomials ... which in turn should remind you of generating functions ... Cn = (1/(n+1))(2n n) The purpose of math is to create models that simplify (which is, however, why they hold only tentatively). When there is no closed-form solution, then the recurrence relation may feel unsatisfactory because it has not led to the desired simplification, but has simply reproduced, redenoted the original problem. pg.233-239 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2214
• Restate* It pays to reread a problem several times. As you rethink classification, hypothesis and conclusion, ask yourself if you can restate what you have already formulated. For example, it may seem that the hypothesis is really trivial, and you just have to repeat it verbatim from the statement of the problem. But if you try to restate it, you may discover new information. Sometimes just reformulating hypothesis and conclusion with new notation helps ... Normally, one reads a problem silently. But for many people, reciting the sequence out loud is enough of a restatement to inspire the correct solution (as long as a number such as "1211" is read "one-two-one-one"...) pg.30, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.1427
• Shifted sequence* Let f(x) = a0 + a1 x + a2 x**2 + ... be the generating function corresponding to the sequence (aN). Now look at x f(x) = a0x + a1 x**2 + a2 x**3 + ... This is the generating function of the original sequence, but shifted.... Now we make use of the relationship between aN and a(N-1)... [Then compare and subtract and rephrase the resulting infinite geometric series.] ... This method was technically messy, since it involved using the geometric-series tool repeatedly as well as partial fractions. But don't get overwhelmed by the technical details - it worked because multiplying a generating function by x produced the generating function for the "shifted" sequence. Likewise, dividing by x will shift the sequence in the other direction. These techniques can certainly be used for many kinds of recurrences. pg.146, The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2166
• Solve for the limit* There is a simple but very productive tool that often works when a sequence is defined recursively. Let us apply it to the previous example: x_n+1 = 1/2(x_n + alpha/x_n) If xn approaches L, then for really large n, both xn and x_n+1 approach L. Thus, as n approaches infinity, the equation x_n+1 = (x_n + alpha/x_n)/2 becomes L = (1/2)(L + alpha/L), and a tiny bit of algebra yields L = square root of alpha. This solve for the limit tool does not prove that the limit exists, but it does show us what the limit must equal if it exists. pg.288 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc2237
• Telescope* A geometric sequence is exactly like an arithmetic sequence except that now the consecutive terms have a common ratio ... a, ar, ar**2, ar**3... The Gaussian pairing tool is no help for summing geometric series, because the terms are not additively symmetric. However, the wonderful telescope tool comes to the rescue .... S = a + ar + ar**2 + ... + ar**(n-1) and rS = ar + ar**2 + ar**3 + ... + ar**n. Observe that S and rS are nearly identical, and hence subtracting the two quantities will produce something really simple ... all terms cancel except for the first and the last. (That's why it's called "telescoping", because the expression "contracts" the way some telescopes do.) We have S - rS = a - ar**n and solving for S yields S = (a - ar**n)/(1-r). ... The important thing is to be aware of the possibility for telescoping, which is really just an application of the adding zero creatively tool. And quite often, a telescoping attempt won't work perfectly, but will reduce the complexity of a problem. pg.173-174 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2180
• Telescoping tool* 78
• Zeta Function* The zeta function z(s) is defined by the infinite series z(s) = 1/1**s + 1/2**s + 1/3**s + ... pg.177 The Art and Craft of Problem Solving, Paul Zeitz, 1999, John Wiley & Sons, Inc.2183
• Stitching together. Apibrėžti "gebėjimus" ir kaip matematinis mąstymas suveda skirtingus gebėjimus suvokti kelis, keliolika, keliasdešimts, tūkstančius ir t.t. daiktų