# Discrete Derivative

Standard

I came across the following interesting question in the book “Math Girls” by Hiroshi Yuki :

Develop a definition for the differential operator $\Delta$ in discrete space,corresponding to the definition of the differential operator D in the continuous space.

We know that derivative of a function f at point x is the rate at which f changes at the point x . Geometrically, derivative at a point x is the slope of the tangent to the function f at x where a tangent is the limit of the secant lines as shown below :

But this happens only in the continuous world where x “glides smoothly” from one point to another. But this is not the case in a discrete world. In the discrete world there is nothing like “being close to each other”. Hence we cannot use the earlier definition of bringing h arbitrarily close to x. In a discrete world we cannot talk about getting “close” to something but instead we can talk about being “next” to each other.

We can talk about the change in x as it moves from x to x+1 while f changes from f(x) to f(x+1). We do not need limits here, so the definition of “difference operator” (analogous to differential operator ) will be :

$\Delta f(x) = \frac{ f(x+1) - f(x) }{(x+1) - x} = f(x+1) - f(x)$

Hence to find derivative of a function, say $g(x) = x^2$ , it is easy to verify that $Dg(x) = 2x$ but $\Delta g(x) = 2x + 1$ (using definitions mentioned above)

Now, when will we be able to get the same derivative in both discrete and continuous worlds? I read a little about this question in math girls and a little more in “An introduction to the calculus of finite differences” by C.H.Richardson.

Calculus of differences is the study of the relations that exist between the values assumed by the function whenever the independent variable takes on a series of values in arithmetic progression.

Let us write f(x) as $f_x$ instead from now onwards. So $f(x+1) - f(x) = \Delta f(x) = f_{x+1} - f_x$. Using above definition we can prove the following for functions $U_x$ and $V_x$ :

1) $\Delta^{k+1} U_x = \Delta^{k} U_{x+1} - \Delta^{k} U_x$

2) $\Delta (U_x + V_x) = \Delta U_x + \Delta V_x$ (or) $\Delta^k (U_x + V_x) =\Delta^k U_x + \Delta^k V_x$

3) $\Delta^k (cU_x) = c \Delta^k U_x$

Theorem. $\Delta^n x^n = n!$

Proof. $\Delta x^n = (x+1)^n - x^n = n\cdot x^{n-1} + \text{terms of degree lower than} (n - 1)$. Each repetition of the process of differencing reduces the degree by one and also adds one factor to the succession $n(n - 1) (n - 2) \cdots$. Repeating the process $n$ times we have $\Delta^k x^n = n!$.

Corollary 1. $\Delta^n ax^n = a\cdot n!$

Corollary 2. $\Delta^{n+1} x^n = 0$

Corollary 3. If $U_x$ is a polynomial of degree n i.e. $U_x= a_0+ a_1 x + a_3 x + \ldots + a_n x^n$ , then $\Delta^n U_x = a_n\cdot n!$.

We call the continued products $U_x^{|n|} = U_x\cdot U_{x+1}\cdot U_{x+2} \cdots U_{x+(n-1)}$ and $U_x^{(n)} = U_x \cdot U_{x-1}\cdot U_{x-2}\cdots U_{x-(n-1)}$ as factorial expressions.

If $U_x$ is the function ax+b for some real numbers a and b, then the factorial forms we get by replacing $U_x$ by ax+b is $(ax+b)^{|n|} = (ax+b)\cdot(a(x+1)+b)\cdot (a(x+2)+b)\cdots (a(x+n-1)+b)$ and $(ax+b)^{(n)} =(ax+b)\cdot (a(x-1)+b)\cdot (a(x-2)+b)\cdots (a(x-(n-1))+b)$.

We define $(ax+b)^{|0|}$ and $(ax+b)^{(0)}$ as 1.

Using the above definition of factorial we can show the following :

(i) $\Delta (ax+b)^{(n)} = a\cdot n \cdot (ax+b)^{(n-1)}$

(ii) $\displaystyle{\Delta \frac{1}{(ax+b)^{|n|}} = \frac{-an}{(ax+b)^{|n+1|}}}$

When we consider the special case of a=1 and b=0, the factorial representations are called raising and falling factorials :

$x^{|n|} = x \cdot (x+1)\cdot (x+2)\cdots (x+n-1)$ – rising factorial

$x^{(n)} =x\cdot (x-1) \cdot (x-2) \cdots (x-n+1)$ – falling factorial.

Substituting a=1 and b=0 in (i) and (ii) above , we get that

$\Delta x^{(n)} = n\cdot x^{(n-1)}$ , $\Delta^n x^{(n)} = n!$ and $\displaystyle{\Delta \frac{1}{x^{|n|}} = - \frac{n}{x^{|n+1|}}}$.

Summary:

source: Richardson, C. H. An introduction to the calculus of finite differences. pp. 10.

Due to the fact that $x^{(n)}$ plays in the calculus of finite differences a role similar to that played by $x^n$ in the infinitesimal calculus, for many purposes in finite differences it is advisable to express a given polynomial in a series of factorials. A method of accomplishing this is contained in Newton’s Theorem.

source: Richardson, C. H. An introduction to the calculus of finite differences. pp. 10.

Since these differences and $U_x$ are identities, they are true for all values of x, and consequently must hold for x = 0. Setting x = 0 in the given function and the differences, we have the required values for all $a_i$ and theorem is proved.

# Number Devil

Standard

If you enjoyed reading Lewis Carroll’s Alice’s Adventures in Wonderland, George Gamow’s Mr Tompkins, Abbott’s Flatland, Malba Tahan’s The Man Who Counted, Imre Lakatos’s Proofs and Refutations or Tarasov’s Calculus, then you will enjoy reading Enzensberger’s The Number Devil. But that is not an if and only if statement.

Originally written in German and published as Der Zahlenteufel, so far it has been translated into 26 languages (as per the back cover).

After reading this book one will have some knowledge of infinity, infinitesimal, zero, decimal number system, prime numbers (sieve of eratothenes, Bertrand’s postulate, Goldbach conjecture), rational numbers (0.999… = 1.0, fractions with 7 in denominator), irrational numbers (√2 = 1.4142…, uncountable), triangular numbers, square numbers, Fibonacci numbers, Pascal’s triangle (glimpse of Sierpinski triangle in it), combinatorics (permutations and combinations, role of Pascal’s triangle), cardinality of sets (countable sets like even numbers, prime numbers,…), infinite series (geometric series, harmonic series), golden ratio (recursive relations, continued fractions..), Euler characteristic (polyhedra and planar graphs), how to prove (11111111111^2 does not give numerical palindrome, Principia Mathematica), travelling salesman problem, Klein bottle, types of infinities (Cantor’s work), Euler product formula, imaginary numbers (Gaussian integer), Pythagoras theorem, lack of women mathematicians  and pi.

Since this is a translation of original work into English, you might not be happy with the language.  Though the author is not a mathematician, he is a well-known and respected European intellectual and author with wide-ranging interests. He gave a speech on mathematics and culture, “Zugbrücke außer Betrieb, oder die Mathematik im Jenseits der Kultur—eine Außenansicht” (“Drawbridge out of order, or mathematics outside of culture—a view from the outside”), in the program for the general public at  the International Congress of Mathematicians in Berlin in 1998. The speech was published under the joint sponsorship of the American Mathematical Society and the Deutsche Mathematiker Vereinigung as a pamphlet in German with facing English translation under the title Drawbridge Up: Mathematics—A Cultural Anathema, with an introduction by David Mumford.

# How to deal with failure?

Standard

If you are an average student (like me…) and are part of an insane curriculum (like having 5 advanced math courses in one semester) you may fail in few of your courses at college, even after trying your best to pass them.  In such situations you may be able to control your panic by reading this Reddit post:

I will suggest you to go through the comments of that post.

# So many Integrals – II

Standard

As promised in previous post, now I will briefly discuss the remaining two flavors of Integrals.

Stieltjes Integral

Stieltjes

In 1894, a Dutch mathematician, Thomas Stieltjes, while solving the moment problem, that is, given the moments of all orders of a body, find the distribution of its mass, gave a generalization of the Darboux integral.

Let $P : a = x_0 < x_1 < x_2<\ldots < x_n = b$, $n$ being an integer, be a partition of the interval $[a, b]$.

For a function $\alpha$, monotonically increasing on $[a,b]$, we write:

$\Delta \alpha_i = \alpha(x_i) - \alpha(x_{i-1})$

Let $f$ be a bounded function defined on an interval $[a, b],\quad a, b$ being real numbers. We define the sum

$S_P = \sum_{i=1}^n f(t_i)\Delta \alpha_i, \quad \overline{S}_P = \sum_{i=1}^n f(s_i)\Delta \alpha_i$

where $t_i,s_i \in [x_{i-1} , x_i]$ be such that

$f(t_i) = \text{sup} \{ f(x) : x \in [x_{i-1}, x_{i}]\}$,

$f(s_i) = \text{inf} \{ f(x) : x \in [x_{i-1}, x_{i}]\}$

If the $\text{inf}\{S_P\}$ and $\text{sup}\{\overline{S}_P\}$ are equal, we denote the common value by  $\int_{a}^{b} f(x) d\alpha(x)$ and call it Steiltjes integral of $f$ with respect to $\alpha$ over $[a,b]$.

Lebesgue Integral

Lebesgue

Let me quote Wikipedia article:

The integral of a function f between limits a and b can be interpreted as the area under the graph of f. This is easy to understand for familiar functions such as polynomials, but what does it mean for more exotic functions? In general, for which class of functions does “area under the curve” make sense? The answer to this question has great theoretical and practical importance.

In 1901, a French mathematician, Henri Léon Lebesgue generalized the notion of the integral by extending the concept of the area below a curve to include functions with uncountable discontinuities .

Lebesgue defined his integral by partitioning the range of a function and summing up sets of x-coordinates belonging to given y-coordinates, rather than, as had traditionally been done, partitioning the domain.

Lebesgue himself, according to his colleague, Paul Montel, compared his method with paying off a debt: (see:pp. 803,  The Princeton Companion to Mathematics)

I have to pay a certain sum, which I have collected in my pocket. I take the bills and coins out of my pocket and give them to the creditor in the order I find them until I have reached the total sum. This is the Riemann integral. But I can proceed differently. After I have taken all the money out of my pocket I order the bills and coins according to identical values and then I pay the several heaps one after the other to the creditor. This is my integral.

A set $\mathcal{A}$ is said to be Lebesgue measurable, if for each set $\mathcal{E} \subset \mathbb{R}$ the Carathéodory condition:

$m^{*} (\mathcal{E}) = m^{*}(\mathcal{E} \cap \mathcal{A}) + m^{*}(\mathcal{E}\backslash \mathcal{A})$

is satisfied, where $m^{*}(\mathcal{A})$ is called outer measure and is defined as:

$m^{*}(\mathcal{A}) = \inf\sum\limits_{n=1}^\infty (b_n-a_n)$

where $\mathcal{A}$ is a countable collection of closed intervals $[a_n,b_n], a_n\leq b_n$, that cover $\mathcal{A}$.

The Lebesgue integral of a simple function $\phi(x) = \sum_{i=1}^n c_i \chi_{\mathcal{A}_i} (x)$ on $\mathcal{A}$, where $\mathcal{A}=\bigcup_{i=1}^{\infty} \mathcal{A}_{i}$, $\mathcal{A}_i$ are pairwise disjoint measurable sets and $c_1, c_2, \ldots$ are real numbers, is defined as:

$\int\limits_{\mathcal{A}} \phi dm = \sum\limits_{i=1}^{n} c_i m(\mathcal{A}_i)$

where, $m(\mathcal{A}_i)$ is the Lebesgue measure of a measurable set $\mathcal{A}_i$.

An extended real value function $f: \mathcal{A}\rightarrow \overline{\mathbb{R}}$ defined on a measurable set $\mathcal{A}\subset\mathbb{R}$ is said to be Lebesgue measurable on $\mathcal{A}$ if $f^{-1} ((c,\infty]) = \{x \in\mathcal{A} : f(x) > c\}$ is a Lebesgue measurable subset of $\mathcal{A}$ for every real number $c$.

If $f$ is Lebesgue measurable and non-negative on $\mathcal{A}$ we define:

$\int\limits_{\mathcal{A}} f dm = \sup \int\limits_{\mathcal{A}} \phi dm$

where the supremum is taken over all simple functions $\phi$ such that $0\leq \phi \leq f$.

The function $f$ is said to be Lebesgue integrable on $\mathcal{A}$ if it’s integral over $\mathcal{A}$ is finite.

The Lebesgue integral is deficient in one respect. The Riemann integral generalizes to the improper Riemann integral to measure functions whose domain of definition is not a closed interval. The Lebesgue integral integrates many of these functions, but not all of them.

# So many Integrals – I

Standard

We all know that, area is  the basis of integration theory, just as counting is basis of the real number system. So, we can say:

An integral is a mathematical operator that can be interpreted as an area under curve.

But, in mathematics we have various flavors of integrals named after their discoverers. Since the topic is a bit long, I have divided it into two posts. In this and next post I will write their general form and then will briefly discuss them.

Cauchy Integral

Newton, Leibniz and Cauchy (left to right)

This was rigorous formulation of Newton’s & Leibniz’s idea of integration, in 1826 by French mathematician, Baron Augustin-Louis Cauchy.

Let $f$ be a positive continuous function defined on an interval $[a, b],\quad a, b$ being real numbers. Let $P : a = x_0 < x_1 < x_2<\ldots < x_n = b$, $n$ being an integer, be a partition of the interval $[a, b]$ and form the sum

$S_p = \sum_{i=1}^n (x_i - x_{i-1}) f(t_i)$

where $t_i \in [x_{i-1} , x_i]f$ be such that $f(t_i) = \text{Minimum} \{ f(x) : x \in [x_{i-1}, x_{i}]\}$

By adding more points to the partition $P$, we can get a new partition, say $P'$, which we call a ‘refinement’ of $P$ and then form the sum $S_{P'}$.  It is trivial to see that $S_P \leq S_{P'} \leq \text{Area bounded between x-axis and function}f$

Since, $f$ is continuous (and positive), then $S_P$ becomes closer and closer to a unique real number, say $kf$, as we take more and more refined partitions in such a way that $|P| := \text{Maximum} \{x_i - x_{i-1}, 1 \leq i \leq n\}$ becomes closer to zero. Such a limit will be independent of the partitions. The number $k$ is the area bounded by function and x-axis and we call it the Cauchy integral of $f$ over $a$  to $b$. Symbolically, $\int_{a}^{b} f(x) dx$ (read as “integral of f(x)dx from a to b”).

Riemann Integral

Riemann

Cauchy’s definition of integral can readily be extended to a bounded function with finitely many discontinuities. Thus, Cauchy integral does not require either the assumption of continuity or any analytical expression of $f$ to prove that the sum $S_p$ indeed converges to a unique real number.

In 1851, a German mathematician, Georg Friedrich Bernhard Riemann gave a more general definition of integral.

Let $[a,b]$ be a closed interval in $\mathbb{R}$. A finite, ordered set of points $P :\{ a = x_0 < x_1 < x_2<\ldots < x_n = b\}$, $n$ being an integer, be a partition of the interval $[a, b]$. Let, $I_j$ denote the interval $[x_{j-1}, x_j], j= 1,2,3,\ldots , n$. The symbol $\Delta_j$ denotes the length of $I_j$. The mesh of $P$, denoted by $m(P)$, is defined to be $max\Delta_j$.

Now, let $f$ be a function defined on interval $[a,b]$. If, for each $j$, $s_j$ is an element of $I_j$, then we define:

$S_P = \sum_{j=1}^n f(s_j) \Delta_j$

Further, we say that $S_P$ tend to a limit $k$ as $m(P)$ tends to 0 if, for any $\epsilon > 0$, there is a $\delta >0$ such that, if $P$ is any partition of $[a,b]$ with $m(P) < \delta$, then $|S_P - k| < \epsilon$ for every choice of $s_j \in I_j$.

Now, if $S_P$ tends to a finite limit as $m(P)$ tends to zero, the value of the limit is called Riemann integral of $f$ over $[a,b]$ and is denoted by $\int_{a}^{b} f(x) dx$

Darboux Integral

Darboux

In 1875, a French mathematician, Jean Gaston Darboux  gave his way of looking at the Riemann integral, defining upper and lower sums and defining a function to be integrable if the difference between the upper and lower sums tends to zero as the mesh size gets smaller.

Let $f$ be a bounded function defined on an interval $[a, b],\quad a, b$ being real numbers. Let $P : a = x_0 < x_1 < x_2<\ldots < x_n = b$, $n$ being an integer, be a partition of the interval $[a, b]$ and form the sum

$S_P = \sum_{i=1}^n (x_i - x_{i-1}) f(t_i), \quad \overline{S}_P =\sum_{i=1}^n (x_i - x_{i-1}) f(s_i)$

where $t_i,s_i \in [x_{i-1} , x_i]$ be such that

$f(t_i) = \text{sup} \{ f(x) : x \in [x_{i-1}, x_{i}]\}$,

$f(s_i) = \text{inf} \{ f(x) : x \in [x_{i-1}, x_{i}]\}$

The sums $S_P$ and $\overline{S}_P$ represent the areas and  $S_P \leq \text{Area bounded by curve} \leq \overline{S}_P$. Moreover, if $P'$ is a refinement of $P$, then

$S_p \leq S_{P'} \leq \text{Area bounded by curve} \leq \overline{S}_{P'} \leq \overline{S}_{P}$

Using the boundedness of $f$, one can show that $S_P, \overline{S}_P$ converge as the partition get’s finer and finer, that is $|P| := \text{Maximum}\{x_i - x_{i-1}, 1 \leq i \leq n\} \rightarrow 0$, to some real numbers, say $k_1, k_2$ respectively. Then:

$k_l \leq \text{Area bounnded by the curve} \leq k_2$

If $k_l = k_2$ , then we have $\int_{a}^{b} f(x) dx = k_l = k_2$.

There are two more flavours of integrals which I will discuss in next post. (namely, Stieltjes Integral and Lebesgue Integral)

# What is Analysis?

Standard

I do not know how to re-produce proofs in Analysis exams, but in this post I will try to know why we study Analysis. Most of us believe that Analysis is same as rigorous Calculus. Also, what makes Mathematics different from Physics is the “rigour”. But, why mathematicians worry so much about rigour? To understand answers of this question one need to understand, what is called “Analysis” in mathematics?

A standard definition of Analysis is (as in [R]):

Analysis is the systematic study of real and complex-valued continuous functions.

The above definition tells us what we will achieve by application of our understanding of Analysis, but this doesn’t explains what “Analysis” itself is.

Clearly, analysis has its roots in calculus. Newton and Leibniz defined differentiation and integration without bothering about definition of limit. Euler found correct value of limit of various infinite series by implicitly assuming “Algebra of infinite series”, which doesn’t exist! I myself used the commutativity of addition of real numbers for the terms in infinite series by assuming “Algebra of infinite series”!! Great mathematicians like Euler, Laplace etc. who even solved differential equations never bothered to think about foundations of calculus because they studied only real variable functions arising from physical problems and series which are power series.

Though without bothering about foundations, we could easily (intuitively) arrive at correct answers due to deep insights (of great mathematicians) but it became extremely difficult to teach such “deep insight” based mathematics to students. Without sense of rigour it became difficult to prove our claims for general cases (like the difference between point-wise continuity and uniform continuity).
This lead to a belief that:

Calculus (and thus Mathematics) is as good as theory of ghosts i.e. without any basis.

Also it became impossible for mathematicians to apply techniques of calculus beyond physical situations i.e. generalization of concepts was not possible.

To get rid of such allegations, Lagrange suggested that the only way to make calculus rigorous is to reduce it to Algebra (since algebra has inherent power of generalization). To illustrate this he defines derivative of a real function, $f'(x)$ as coefficient of the linear term in $h$ in Taylor series expansion for $f(x+h)$. Again this was wrong without consideration of limits and convergence, since there is no “Algebra of infinite series”!!! But this idea of using Algebra to make calculus rigorous was successfully realized by Cauchy, he used “Algebra of Inequalities” (but he also implicitly assumed the completeness property of real numbers) by introducing $\epsilon$ and $\delta$ (though not explicitly, but in words).

How “Algebra of Inequalities” became technique to create “rigorous calculus”, which we know as “Analysis” ? One main part of calculus was “Approximations”, i.e. to compute an upper bound on the error in the approximation — that is, the difference between the sum of the series and the $n^{th}$ partial sum. Thus the “Tool of Approximation” was transformed to “tool of rigour”.

Initially, integral was thought as inverse of differential. But sometimes the inverse could not be computed exactly, so Euler remarked that the integral could be approximated as closely as one liked by a sum (also the geometric picture of an area being approximated by rectangles). Again, we got better definition of integral by work done by various mathematicians to approximate the values of definite integrals. Poisson, was interested in complex integration and was concerned about behaviour and existence of integrals. He stated and proved  “The fundamental proposition of the theory of definite integrals”. He proved it by using an inequality-result: the Taylor series with remainder. This was the first attempt to prove the equivalence of the antiderivative and limit-of-sums conceptions of the integral. But, Poission implicitly assumes the existence of antiderivatives and bounded first derivatives for $f$ on the given interval, thus the proof assumes that the subintervals on which the sum is taken are all equal. Again, Cauchy added rigour to Poisson’s proof.

Since most algebraic formulas hold only under certain conditions, and for certain values of the quantities they contain, one could not assume that what worked for finite expressions automatically worked for infinite ones. Also,  just because there was an operation called “taking a derivative” did not mean that the inverse of that operation always produced a result. The existence of the definite integral had to be proved. Borrowing from Lagrange the mean value theorem for integrals, Cauchy finally proved the “Fundamental Theorem of Calculus”.

Thus, algebraic approximations produced the algebra of inequalities. The application of Algebra of inequalities lead to concept of Approximations in Calculus. The concept of approximations in calculus in turn lead to 3 key concepts : “error bounds for series” (d’Alembert), “inequalities about derivatives” (Lagrange) and “approximations to integrals” (Euler). I believe that, these three concepts combined with rigour lead to what we call “Analysis” in Mathematics.

The subject of analysis itself consists of 4 main flavours:

• Real Analysis
• Complex Analysis
• Functional Analysis
• Harmonic Analysis

with the generalization of basic tools in terms of measure theory (leading to generalization of integration) and calculus of several variables.  For example, the differentiation of a several variable function $f: \Omega \to \mathbb{R}^m$ where $\Omega \subset \mathbb{R}^n$ leads to a linear transformation from $\mathbb{R}^n$ to $\mathbb{R}^m$ (or equivalently, an $m\times n$ matrix with real values entries) instead of a real number with norm of limiting value in denominator. Also, we can generalize the concept of Taylor series for several variable functions using the notion of “partial derivatives” as

$\displaystyle{T(x_1,\ldots,x_d) = \sum_{n_1=0}^\infty \cdots \sum_{n_d = 0}^\infty \frac{(x_1-a_1)^{n_1}\cdots (x_d-a_d)^{n_d}}{n_1!\cdots n_d!}\,\left(\frac{\partial^{n_1 + \cdots + n_d}f}{\partial x_1^{n_1}\cdots \partial x_d^{n_d}}\right)(a_1,\ldots,a_d) }$

Using the “change of variable theorem” we can evaluate integrals of several variable functions over a “cell” by evaluating multiple integrals. Finally, using the concept of “differential forms”originating from geometry,  we can prove Stokes’ theorem, of which “fundamental theorem of calculus” turns out to be a special case (among many other important theorems like Green’s theorem and Divergence theorem).

References:
[G] J V Grabiner, “Who Gave You the Epsilon? Cauchy and the Origins of Rigorous Calculus”, American Mathematical Monthly 90 (1983), 185–194

[R] John Renze and Eric W. Weisstein, “Analysis.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/Analysis.html

[S] Ian Stewart,  “analysis | mathematics”. Encyclopedia Britannica.
http://www.britannica.com/topic/analysis-mathematics

[X] Mathematical analysis. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Mathematical_analysis&oldid=31489

[SM] Maurice Sion, History of measure theory in the twentieth century, www.math.ubc.ca/~marcus/Math507420/Math507420hist.pdf

[H] Barbara Hubbard and John H. Hubbard, “Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach”, Prentice Hall .