Matrices and the Pacal Triangle

Create a matrix from the first n rows of the Pascal Triangle like

1 0 0 0
1 1 0 0
1 2 1 0
1 3 3 1

Then the inverse of this matrix is...

1 0 0 0
-1 1 0 0
1 -2 1 0
-1 3 -3 1

Discrete Mathematics Using Latin Squares

A truly beautiful mathematics book. A book that demands to be read, studied, worked! I will. I love it already. Happiness is easy.

In the past two decades, researchers have discovered a range of uses for Latin squares that go beyond standard mathematics. People working in the fields of science, engineering, statistics, and even computer science all stand to benefit from a working knowledge of Latin squares. Discrete Mathematics Using Latin Squares is the only upper-level college textbook/professional reference that fully engages the subject and its many important applications.

Fibonacci sequence in the Pascal triangle

Where is the Fibonacci sequence in 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

Count as follows.
Start left with a 1.
While on a number:
- Move right
- Move up
- Add to running total.

Let's go.
First row.
1.
Stop.

Second row.
1
Stop.

Third row.
1, right, up
1
Stop.

Fourth row
1, right, up
2
Stop.

Fifth row
1, right, up
3, right, up
1
Stop.

Sixth row
1, right, up
4, right, up
3
Stop.

Totals were 1, 1, 2, 3, 5, 8.

Fibonacci sequence, obvious.

Now what's the proof?

Discrete Mathematics video

I watched video 11-15-00: Combinations and permutations. A lecture by Shai Simonson. A lecture in the Discrete Mathematics series on the ADUni.org website.

Topics:
Counting principles.
- Multiplication
- Addition
- Complement
- Counting double
- 'When are things the same'?
Permutation
Combination
n Choose k.
Binomial Theorem
Pascal Triangle
Proofs
- by formula
- by induction
- by combinatorial argument

Doing proofs by combinatorial argument is a powerful technique. The basic identity from 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
...
[n,k]=[n-1,k-1]+[n-1,k]
for example
[6,3]=[5,2]+[5,3]=20=10+10
can easily proven by a combinatorial argument.

Such an argument could be the following.
Let n be the number of employees of a small company with one director. We have to select a k-member team from all employees. The number of teams is [n,k]
Exclude the director from selection and select a k-member team. The number of teams is [n-1,k].
Now select a (k-1)-team, the number of teams is [n-1,k-1] and add the director to it which makes it a k-member team including the director.
Adding the number of k-member teams without a director and k-member teams with a director is the total number of k-member teams or [n-1,k] + [n-1, k-1].

This proves [n,k]=[n-1,k-1]+[n-1,k].