View source for Pascal's Triangle and its patterns and properties

= Pascal's Identity =
== Identity ==
Pascal's Identity states that

<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>

for any positive integers <math>k</math> and <math>n</math>.  Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = nCk = C_k^n</math>.

Remember that <math>\binom{n}{r}=\frac{n!}{k!(n-k)!}.</math>

== Proving it ==
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is pretty clear.
So assume <math>k \leq n</math>.  Then

<cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\
&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\
&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\
&=&\frac{n!}{k!(n-k)!}\\
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath>
There we go. We proved it!

== Why is it needed? ==
It's mostly just a cool thing to know. However, if you want to know how to use it in real life go to https://artofproblemsolving.com/videos/counting/chapter12/141. Or really any of the counting and probability videos.

= Introduction to Pascal's Triangle =
== How to build it ==
Pascal's Triangle is a triangular array of numbers in which you start with two infinite diagonals of ones and each of the rest of the numbers is the sum of the two numbers above it. It looks something like this:
                                          1
                                         1 1
                                        1 2 1
                                       1 3 3 1
                                      1 4 6 4 1
And on and on...

== Combinations ==
=== Combinations ===
Pascal's Triangle is really combinations. It looks something like this if it is depicted as combinations:

                              <math>\binom{0}{0}</math>                        
                 <math>\binom{1}{0}</math>                  <math>\binom{1}{1}</math>
    <math>\binom{2}{0}</math>                     <math>\binom{2}{1}</math>                <math>\binom{2}{2}</math>

And on and on...

=== Proof ===

If you look at the way we build the triangle, each number is the sum of the two numbers above it. Assuming that these combinations are true then each combination in the sum of the two combinations above it. In an equation, it would look something like this:   <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>. Its Pascals Identity! Therefore each row looks something like this:

<math>\binom{n}{0}   \binom{n}{1}   \binom{n}{2} ... \binom{n}{n}</math>

= Patterns and Properties =
In addition to combinations, ''Pascal's Triangle'' has many more patterns and properties. See below. Be ready to be amazed.  
== Binomial Theorem ==
Let's multiply out some binomials. Try it yourself and it will not be fun:
<math>(x+y)^0=1</math>

<math>(x+y)^1=1x+1y</math>

<math>(x+y)^2=1x^2+2xy+1y^2</math>

<math>(x+y)^2=1x^3+3x^2y+3y^2x+1^3</math>

If you take away the x's and y's you get:

          1
         1 1
        1 2 1
       1 3 3 1     
It's ''Pascal's Triangle''!

=== Proof ===
There are a number of different ways to prove the Binomial Theorem, for example by a straightforward application of mathematical induction. The Binomial Theorem also has a nice combinatorial proof:

We can write <math>(a+b)^n=\underbrace{ (a+b)\cdot(a+b)\cdot(a+b)\cdot\cdots\cdot(a+b) }_{n}</math>. Repeatedly using the distributive property, we see that for a term <math>a^m b^{n-m}</math>, we must choose <math>m</math> of the <math>n</math> terms to contribute an <math>a</math> to the term, and then each of the other <math>n-m</math> terms of the product must contribute a <math>b</math>. Thus, the coefficient of <math>a^m b^{n-m}</math> is the number of ways to choose <math>m</math> objects from a set of size <math>n</math>, or <math>\binom{n}{m}</math>. Extending this to all possible values of <math>m</math> from <math>0</math> to <math>n</math>, we see that <math>(a+b)^n = \sum_{m=0}^{n}{\binom{n}{m}}\cdot a^m\cdot b^{n-m}</math>, as claimed.

Similarly, the coefficients of <math>(x+y)^n</math> will be the entries of the <math>n^\text{th}</math> row of Pascal's Triangle. This is explained further in the Counting and Probability textbook [AoPS]
=== In real life ===
It is really only used for multipling out binomials. More usage at 
https://artofproblemsolving.com/videos/counting/chapter14/126.
== Powers of 2 ==
=== Theorem ===
==== Theorem ====
It states that <math>\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n</math>

==== Why do we need it? ====
It is useful in many word problems (That means, yes, you can use it in real life) and it is just a cool thing to know. More at https://artofproblemsolving.com/videos/mathcounts/mc2010/419.
=== Proof ===
==== Subset proof ====
Say you have a word with n letters. How many subsets does it have in terms of n? Here is how you answer it: You ask the first letter Are you in or are you out? Same to the second letter. Same to the third. Same to the n. Each of the letters has two choices: In and Out. The would be <math>(2)(2)(2)(2)</math>...n times. <math>2^n</math>.

==== Alternate proof ====
If you look at the way we built the triangle you see that each number is row n-1 is added on twice in row n. This means that each row doubles. That means you get powers of two.

== Triangle Numbers ==
=== Theorem ===
If you look at the numbers in the third diagonal you see that they are triangle numbers.
=== Proof ===
Now we can make an equation: <math>\binom{n}{2}=1+2+3+...+(n-1) \Rightarrow \binom{n}{2}=\frac{n(n+1)}{2} \Rightarrow \frac{n!}{2!(n-2)!}=\frac{n(n+1)}{2} \Rightarrow \frac{n(n+1)}{2}=\frac{n(n+1)}{2}</math>

== Hockey stick ==
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.


<asy>
int chew(int n,int r){
 int res=1;
 for(int i=0;i<r;++i){
  res=quotient(res*(n-i),i+1);
  }
 return res;
 }
for(int n=0;n<9;++n){
 for(int i=0;i<=n;++i){
  if((i==2 && n<8)||(i==3 && n==8)){
   if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}
   else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}
   }
  else{
   label(string(chew(n,i)),(11+n/2-i,-n));
   }
  }
 }
</asy>

This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed.


===Proof===

'''Inductive Proof'''

This identity can be proven by induction on <math>n</math>.

<u>Base Case</u>
Let <math>n=r</math>.

<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.

<u>Inductive Step</u>
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.

'''Algebraic Proof'''

It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.
Note that

<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.

'''Combinatorial Proof 1'''

Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.

'''Combinatorial Proof 2'''

We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people.  We can divide this into <math>n-k+1</math> disjoint cases.  In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee.  This can be done in <math>\binom{n-x+1}{k}</math> ways.  Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath>

= See Also =
== AoPS Wiki ==

- [[Pascal's Identity]]

- [[Pascal's Triangle]]

- [[Combinatorics]]

- [[Hockey-Stick Identity]]

== Videos ==

- https://artofproblemsolving.com/videos/counting/chapter12/141

- https://artofproblemsolving.com/videos/mathcounts/mc2012/374

- https://artofproblemsolving.com/videos/counting/chapter14/123

- https://artofproblemsolving.com/videos/counting/chapter13/143

- https://artofproblemsolving.com/videos/mathcounts/mc2010/419

= Copied From =
- 50 percent original Colball otherwise known as Colin Friesen
- Pascal's Identity
- Hockey-Stick Identity 
- Pascal's Triangle