Another identity in Pascal's Triangle

On the Pascal Triangle resources website I found, among many other identities, the following two basic identities:

The first one is in every book on discrete math I have seen thus far. And although basic I don't recall to have seen the second identity somewhere else so for me it is a new one.

Michael Pogorsky's proof of Fermat's last theorem

Every now and then I ask the guru's at PlanetMath for help. I did so again today and while I was there I visited the Cafe section in the forum. There was a discussion with a rather long thread about Fermat's last theorem. Because Andrew Wiles proved the theorem with late 20th century mathematics people are still trying to prove the theorem using mathematics from Fermat's days. Every now and again a proof comes up. Usually professional mathematicians don't even bother to look. The mostly unknown authors are called crackpots in mathematical circles. How do these so called 'proofs' look like? Like this for example. It's a proof of Fermat's last theorem by Michael Pogorsky. - Read an analysis of the proof by a PM guru here.

Property of the Pascal Triangle

Another interesting property of the Pascal Triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Since Choose(n,k) = (k+1)/(n-k)*Choose(n,k+1) we get ( for example ) for row 7:
1/7 * 7 = 1
2/6 * 21 = 7
3/5 * 35 = 21
4/4 * 35 = 35
5/3 * 21 = 35
6/2 * 7 = 21
7/1 * 1 = 7

Wolfram 2,3 Turing Machine

News update from Mathematica:

We're excited to announce that the $25,000 Wolfram 2,3 Turing Machine Research Prize has been won.

Alex Smith, a 20-year-old undergraduate in Birmingham, UK, has given a 40-page proof that Wolfram's 2,3 Turing machine is indeed universal.

This result ends a half-century quest to find the simplest possible universal Turing machine.

It also provides strong further evidence for Wolfram's Principle of Computational Equivalence.

The official prize ceremony is planned for November at Bletchley Park, UK, site of Alan Turing's wartime work.

For more information about the prize and the solution, see: http://www.wolframprize.org

Stephen Wolfram has posted his personal reaction to the prize at:
http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html

I am still reading the biography of Alan Turing. I am reading chapter 6 now. World war II has ended and Alan is writing a proposal to get a project for building a general purpose computer ( the first one ever ) funded. He wrote his paper on the Universal Turing Machine long before the war started.

Program for printing a Pascal Triangle:

Using Mathematica ( what else? ):

Pascal[n_]:=MatrixExp[Table[If[i == (j+1),j+1,0],{i,0,n},{j,0,n}]]

Usage: Pascal[n]//MatrixForm

Pascal's Triangle as a Matrix Exponential

For me, this is an amazing result. When I read about it in "Accessing Bernoulli-Numbers by Matrix-Operations, Gottfried Helms 3'2006 Version 2.3" I immediately started Mathematica and tried it myself. The picture above is the result. It's what I call some deep mathematics, although the formula for calculating the Matrix Exponential is easily understood.

Dangerous Knowledge

Dangerous Knowledge is a BBC Four documentary about the lives and work of Georg Cantor, Kurt Godel and Alan Turing. ( Find it on Google Video. ) Cantor, Godel and Turing worked on paradoxical stuff. The paradox about the documentary is that it is about mathematics without showing any of it. I suppose it is a nice documentary if you are familiar with Cantor, Godel and Turing. The documentary in that respect becomes a " complementary ".

Sequences

Sequence
Closed form(ula)
Generating function

{1,1,1,1,...}
a(n)=1
f(x)=1/(1-x)

{1,2,4,8,...}
a(n)=2^n
f(x)=1/(1-2x)

{0,0,0,0,1,1,...}
if (n<4) then a(n)=0 else a(n)=1
f(x)=x^4/(1-x)

See also the Mathematica package RSolve

Generating Functions

Generating functions are one of the most surprising, useful, and clever inventions in discrete mathematics.

Generating functions transform problems about sequences into problems about functions.
For example:
* sequence {1, 4, 9, 16, 25, ... }
* closed form a(n) = n^2
* generating function: F(x)=x(1+x)/(1-x)^3.
Interested? An introduction to generating functions (pdf document) can be found [ here ].

Difference sequences

Rather early in our math education we learn about functions and derivative functions.

  
              f(x+h)-f(x)
f'(x) = lim   -----------
         h-> 0    h 

For example: 
f(x) = x^n
f'(x) = n*x^(n-1)

Something similar can be defined for sequences, in that case the 'derative' is called the difference sequence.

a_n = {1, 16, 81, 256, ... }
f(n) = n^4
f'(n) = 1 + 4n + 6n^2 + 4n^3
f''(n) = 14 + 24n + 12n^2
f(3)(n) = 36 + 24n
f(4)(n) = 24

For an arbitrary sequence f:
f(m)(n) = Sum[(-1)^(k)*Binomial[m,k]*f[n-k+m],{k,0,m}]

Here also we see that Pascal's Triangle has a crucial meaning.

Binomial Theorem

(x + y)^n = Sum(n,k) Choose(n,k) * x^(n-k) * y^k

So what? I can now -prove- it. ( By induction. )

Literary Mathematics

"... A generating function is a clothesline on which we hang up a sequence of numbers for display. ..." ( by Herbert S. Wilf in Generatingfunctionology )