proof

Proof Without Words #2

My last post seemed to go down well so I thought I’d compile a few more images of proofs without words!

C93PNFXXUAAfP7z.png

Determinant is the area of a parallelogram, by Solomon Golomb, Mathematics Magazine, March 1985.

C6fZNSAWUAAdyzq.jpg

Jensen_graph.png

A visual proof of Jensen’s inequality, found on Wikipedia. Jensen’s inequality states that

Screen Shot 2017-05-02 at 7.51.38 AM.png

In the diagram, the dashed curve along the X axis is the hypothetical distribution of X, while the dashed curve along the Y axis is the corresponding distribution of Y values. Note that the convex mapping Y(X) increasingly “stretches” the distribution for increasing values of X.

EXwbl.png

 

Hope you enjoyed! M x

12th Polymath Project

The Polymath Project is a collaboration among mathematicians to solve important problem in mathematics by providing a platform for mathematicians to communicate with each other on how to find the best route to the solution.

It began in January 2009 when Tim Gowers posted a problem on his blog and asked readers to reply with partial ideas or answers. This experiment resulted in a new answer to a difficult problem, proving the benefits of collaboration.

Previous Polymath projects that have successfully led to proofs incude the density version of the Hales-Jewett theorem and the Erdös discrepancy problem, as well as famously reducing the bound on the smallest gaps between primes.

Recently the 12th Polymath Project has started; Timothy Chow of MIT has proposed a new Polymath Project – resolve Rota’s basis conjecture.

What is the Rota’s Basis Conjecture?

The Rota’s Basis Conjecture states:

“If B1, B2,…., Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n x n grid of vectors (vij) such that:

  1. the n vectors in row i are the members of the ith basis Bi (in some order), and
  2. in each column of the matrix, the n vectors in that column form a basis of V.”

Although easy to state, this conjecture has revealed itself hard to prove (like Fermat’s Last Theorem)!

M x

Proof Without Words #1

I decided to start a new series called ‘Proof Without Words’: a collection of pictures which prove a mathematical fact with an image. Remember, these are in no way rigorous and are just meant to give an idea of why the fact is true!

1/2+1/4+1/8+1/16+1/32+ … = 1

Sum of the first n positive odd numbers = n^2

arctan(1) + arctan(2) + arctan(3) = π

Screen Shot 2017-02-21 at 9.21.36 PM.png

Screen Shot 2017-02-21 at 9.22.18 PM.png

Viviani’s Theorem

The sum of the distances from any interior point to the sides of an equilateral triangle equals the length of the triangle’s altitude.

Screen Shot 2017-02-21 at 9.24.11 PM.png

M x

 

Stirling’s Formula

Today I wanted to discuss something I learnt last week in my Probability course: Stirling’s Formula. Stirling’s Formula is an approximation for factorials, and leads to quite accurate results even for small values of n.

The formula can be written in two ways:

{\displaystyle \ln n!=n\ln n-n+O(\ln n)}

or

{\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n},}

where the ~ sign means that the two quantities are asymptotic (i.e. their ratios tend to 1 as n tends to infinity).

File:Mplwp factorial gamma stirling.svg

Comparison of Factorial with Stirling’s Approximation | Source: Wikipedia

Proof of Stirling’s Formula

The following identity arises using integration by parts:

Screen Shot 2017-02-06 at 8.11.00 AM.png

Taking f(x) = log x, we obtain

Screen Shot 2017-02-06 at 8.11.48 AM.png

Next, sum over n, and by recalling that log x + log y = log xy we get the following expression:

Screen Shot 2017-02-06 at 8.12.23 AM.png

where

Screen Shot 2017-02-06 at 8.13.23 AM.png

Next, define

Screen Shot 2017-02-06 at 8.13.38 AM.png

which allows us to rearrange the above expression to:

Screen Shot 2017-02-06 at 8.13.41 AM.png

So as n tends to infinity we get

Screen Shot 2017-02-06 at 8.13.46 AM.png

(*)

How do we show that Screen Shot 2017-02-06 at 8.15.19 AM.png ?

Firstly, note that from (*) it follows that

Screen Shot 2017-02-06 at 8.16.31 AM.png

So, we need to show that

Screen Shot 2017-02-06 at 8.16.57 AM.png

Let’s set

Screen Shot 2017-02-06 at 8.17.25 AM.png

Note that I0=π/2 and I1 = 1. Then for n≥2, we can integrate by parts to see that

Screen Shot 2017-02-06 at 8.19.17 AM.png

And so, we obtain the following two expressions:

Screen Shot 2017-02-06 at 8.19.36 AM.png

In is decreasing in n and In/In-2 → 1, so it follows that I2n/I2n+1 → 1. Therefore,

Screen Shot 2017-02-06 at 8.21.18 AM.png

as required.

Although the end result is satisfying, I find that some steps in this proof are like ‘pulling-a-rabbit-out-of-a-hat’! What do you think? Mx

 

 

Fermat’s Little Theorem

Statement:

Let p be a prime then ap ≡ a (mod p), for any natural number a.

Proof using Modular Arithmetic:

Firstly, we need to discuss Wilson’s theorem. This states:

(p-1)! ≡ -1 (mod p) is p is prime.

We must first prove this theorem:

If p is prime, then 1, 2, …, p-1 are invertible mod p. Now we can pair each of these numbers with its inverse (for example 3 with 4 in mod 11). The only elements that cannot be paired with a different number are 1 and -1, which are self-inverses, as shown below:

Screen Shot 2017-01-02 at 6.30.37 PM.png

Now (p-1)! is a product of (p-3)/2 inverse pairs together with -1 and 1, whose product is -1.

So (p-1)! ≡ -1 (mod p).

Back to the proof of Fermat’s Little Theorem.

The statement of Fermat’s Little Theorem is equivalent to ap-1 ≡ 1 (mod p) if a ≢ 0 (mod p).

Consider the numbers a, 2a, …., (p-1)a. These are each distinct mod p and so they are congruent to 1, 2, …., (p-1) (mod p) in some order.

 Hence a·2a···(p-1)a ≡ 1·2···(p-1) (mod p).

So ap-1(p-1)! ≡ (p-1)!.

And therefore ap-1 ≡ 1 (mod p).

We can extend this to a≡ a (mod p) as shown below:

When a ≡ 0 (mod p): 0≡ 0 (mod p). So a≡ a (mod p).

When a ≢ 0 (mod p): We can multiply through by a, as a and p are coprime. Then we get a≡ a (mod p), as required.

Hence, we have proved Fermat’s Little Theorem, a very important result in number theory.

M x

Isoperimetric inequality

The isoperimetric inequality dates back to the olden days, where there was a problem that asked: “Among all closed curves in the plane of fixed perimeter, which curve (if any) maximises the area of its enclosed region?” This is equivalent to asking: “Among all closed curves in the plane enclosing a fixed area, which curve (if any) minimises the perimeter?” The solution to this problem is expressed in the form of an inequality: the isoperimetric inequality.

The isoperimetric inequality is a geometric inequality that involves the square of the circumference of a closed curve in a plane and the area that it encloses in that plane. This inequality states that

4\pi A\leq L^{2},

where L is the length of a closed curve and A is the area of the planar region that it encloses.

Many proofs have been published for this inequality. For example, in 1938 E. Schmidt produced an elegant proof based on “the comparison of a smooth simple closed curve with an appropriate circle”.

An extension of this inequality is the isoperimetric quotient, Q, of a closed curve which is defined in the following way:

Q={\frac  {4\pi A}{L^{2}}}

Hence, it is the ratio of its area and that of a circle with the same perimeter.

The inequality highlights how  Q ≤ 1 and for a circle Q = 1.

M x