Tag Archives: induction

Understanding Geometry – 2

Standard

If you want to brush up your high school geometry knowledge, then KhanAcademy is a good place to start. For example, I learned a new proof of Pythagoras Theorem (there are 4 different proofs on KhanAcademy) which uses scissors-congruence:

In this post, I will share with you few theorems from L. I. Golovina and I. M. Yaglom’s “Induction in Geometry ”  which I learned while trying to prove Midpoint-Polygon Conjecture.

Theorem 1: The sum of interior angles of an n-gon is 2\pi (n-2).

Theorem 2: The number of ways in which a convex n-gon can be divided into triangles by non-intersecting diagonals is given by

\displaystyle{\frac{2(2n-5)!}{(n-1)!(n-3)!}}

Theorem 3: Given a \triangle ABC, with n-1 straight lines CM_1, CM_2, \ldots CM_{n-1} drawn through its vertex C, cutting the triangle into n smaller triangles \triangle ACM_1, \triangle M_1CM_2, \ldots, \triangle M_{n-1}CB. Denote by r_1, r_2, \ldots r_n and \rho_1, \rho_2, \ldots, \rho_n respectively the radii of the inscribed and circumscribed circles of these triangles (all the circumscribed circles are inscribed within the angle C of the triangle) and let r and \rho be the radii of the inscribed and circumscribed circles (respectively) of the \triangle ABC itself. Then

\displaystyle{\frac{r_1}{\rho_1} \cdot\frac{r_2}{\rho_2} \cdots\frac{r_n}{\rho_n} =\frac{r}{\rho} }

Theorem 4: Any convex n-gon which is not a parallelogram can be enclosed by a triangle whose sides lie along three sides of the given n-gon.

Theorem 5 (Levi’s Theorem): Any convex polygon which is not a parallelogram can be covered with three homothetic polygons smaller than the given one.

The above theorem gives a good idea of what “combinatorial geometry” is all about. In this subject, the method of mathematical induction is widely used for proving various theorems. Combinatorial geometry deals with problems, connected with finite configurations of points or figures. In these problems, values are estimated connected with configurations of figures (or points) which are optimal in some sense.

Theorem 6 (Newton’s Theorem): The midpoints of the diagonals of a quadrilateral circumscribed about a circle lie on one straight line passing through the centre of the circle.

Theorem 7 (Simson’s Theorem): Given a \triangle ABC inscribed in the circle S with an arbitrary point P on this circle. Then then feet of the perpendiculars dropped from the point P to the sides of the \triangle ABC are collinear.

We can extend the above idea of Simson’s line to any n-gon inscribed in a circle.

Theorem 8: A 3-dimensional space is divided into \frac{(n+1)(n^2-n+6)}{6} parts by n planes, each three of which intersect and no four of which have a common point.

Theorem 9: Given n spheres in 3-dimesnional space, each four of which intersect. Then all these spheres intersect, i. e. there exists a point belonging to all the spheres.

Theorem 10 (Young’s Theorem): Given n points in the plane such that each pair of them are at a distance of at most 1 from each other. Then all these points can be enclosed in a circle of radius 1/\sqrt{3}.

I won’t be discussing their proofs since the booklet containing the proofs and the detailed discussion is freely available at Mir Books.

Also, I would like to make a passing remark about the existence of a different kind of geometry system, called “finite geometry“. A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. You can learn more about it here: http://www.ams.org/samplings/feature-column/fcarc-finitegeometries

Integration & Summation

Standard

A few months ago I wrote a series of blog posts on “rigorous”  definitions of integration [Part 1, Part 2]. Last week I identified an interesting flaw in my “imagination” of integration in terms of “limiting summation” and it lead to an interesting investigation.

The Paradox

While defining integration as area under curve, we consider rectangles of equal width and let that width approach zero. Hence I used to imagine integration as summation of individual heights, since width approaches zero in limiting case. It was just like extending summation over integers to summation over real numbers.

integration (1)

My Thought Process..

But as per my above imagination, since width of line segment is zero,  I am considering rectangles of zero width. Then each rectangle is of zero area (I proved it recently). So the area under curve will be zero! Paradox!

I realized that, just like ancient greeks, I am using very bad imagination of limiting process!

 

The Insight

But, as it turns out, my imagination is NOT completely wrong.  I googled and stumbled upon this stack exchange post:

There is the answer by Jonathan to this question which captures my imagination:

The idea is that since \int_0^n f(x)dx can be approximated by the Riemann sum, thus \displaystyle{\sum_{i=0}^n f(i) = \int_{0}^n f(x)dx + \text{higher order corrections}}

The generalization of above idea gives us the Euler–Maclaurin formula 

\displaystyle{\sum_{i=m+1}^n f(i) = \int^n_m f(x)\,dx + B_1 \left(f(n) - f(m)\right) + \sum_{k=1}^p\frac{B_{2k}}{(2k)!}\left(f^{(2k - 1)}(n) - f^{(2k - 1)}(m)\right) + R}

where m,n,p are natural numbers, f (x) is a real valued continuous function, B_k are the Bernoulli numbers  (I mumbled about them few weeks ago)  and R is an error term which is normally small for suitable values of p (depends on n, m, p and f).

Proof of above formula is by principle of mathematical induction. For more details, see this beautiful paper: Apostol, T. M.. (1999). An Elementary View of Euler’s Summation Formula. The American Mathematical Monthly, 106(5), 409–418. http://doi.org/10.2307/2589145 

Metamathematics

Standard

I like to predict things going to happen each day based upon some (il)logical reasoning. Also, earlier this year I wrote a blog post: “Inquisitive Mathematical Thinking“.

Today, inspired by various “wrong” interpretation of “Principle of Mathematical Induction” which leads to various absurd results, I came up with an idea of giving a “flawed” proof of (i.e. I will deliberately mimic what I call “rape of Mathematics”):

Every day is good day.

Let me start with following induction Hypothesis:
P(1): Today is a good day.
This is trivially true (just like the statement “the sun rises in east”).

Now, let’s assume the truth of following statement:
P(k): k^{th} day is good day.

Now, what remains to prove is that P(k) \Rightarrow P(k+1), where:
P(k+1): (k+1)^{th} day is good day.

Since, our past actions determine our future results (metaphysical truth), if today is good day then I will be able to prepare for tomorrow’s challenges and hence my tomorrow will be good. Thus proving the inductive step.

————————–
The above proof has lot of logical flaws like: ” How do you define a day to be good?” and “Implication is based on a metaphysical truth”.

Bottom line: Life not as simple as Mathematics!