Difference between revisions of "Power's of 2 in pascal's triangle"
| (26 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | == Pascal's Triangle == | + | = Review = |
| + | |||
| + | == Pascal's Triangle == | ||
Pascal's Triangle is a triangular array of numbers where each number is the sum of the two numbers above it. It Looks something like this: | Pascal's Triangle is a triangular array of numbers where each number is the sum of the two numbers above it. It Looks something like this: | ||
| Line 9: | Line 11: | ||
1 4 6 4 1 | 1 4 6 4 1 | ||
And on and on... | And on and on... | ||
| + | |||
== Patterns and properties == | == Patterns and properties == | ||
| + | |||
| + | === Combanations === | ||
Pascal's Triangle can also be written like this | Pascal's Triangle can also be written like this | ||
| Line 15: | Line 20: | ||
<math>\binom{0}{0}</math> | <math>\binom{0}{0}</math> | ||
<math>\binom{1}{0}</math> <math>\binom{1}{1}</math> | <math>\binom{1}{0}</math> <math>\binom{1}{1}</math> | ||
| − | <math>\binom{2}{0}</math> | + | <math>\binom{2}{0}</math> <math>\binom{2}{1}</math> <math>\binom{2}{2}</math> |
| + | |||
| + | And on and on... | ||
| + | Remember that <math>\binom{n}{r}=\frac{n!}{k!(n-k)!}</math> where <math>n \ge r</math>. | ||
| + | |||
| + | === Sum of rows === | ||
| + | 1 =1 | ||
| + | 1+1 =2 | ||
| + | 1+2+1 =4 | ||
| + | 1+3+3+1 =8 | ||
| + | 1+4+6+4+1 =16 | ||
| + | These are powers of two. (Note: There are dozens of more patterns but it would have nothing to do with powers of two). | ||
| + | |||
| + | = Powers of two = | ||
| + | |||
| + | == 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 is 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. | ||
| + | |||
| + | = Links = | ||
| + | |||
| + | == AoPS links == | ||
| + | |||
| + | https://artofproblemsolving.com/videos/counting/chapter12/141 | ||
| + | https://artofproblemsolving.com/videos/counting/chapter12/140 | ||
| + | https://artofproblemsolving.com/videos/counting/chapter12/142 | ||
| + | https://artofproblemsolving.com/videos/mathcounts/mc2010/419 | ||
| + | |||
| + | == Other links == | ||
| + | |||
| + | http://jwilson.coe.uga.edu/EMAT6680Su12/Berryman/6690/BerrymanK-Pascals/BerrymanK-Pascals.html | ||
| + | https://www.mathsisfun.com/pascals-triangle.html | ||
| + | https://www.cut-the-knot.org/arithmetic/combinatorics/PascalTriangleProperties.shtml | ||
| + | https://en.wikipedia.org/wiki/Pascal%27s_triangle | ||
Latest revision as of 15:57, 16 June 2019
Contents
Review
Pascal's Triangle
Pascal's Triangle is a triangular array of numbers where each number 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...
Patterns and properties
Combanations
Pascal's Triangle can also be written like this
And on and on...
Remember that 
where 
.
Sum of rows
1 =1
1+1 =2
1+2+1 =4
1+3+3+1 =8
1+4+6+4+1 =16
These are powers of two. (Note: There are dozens of more patterns but it would have nothing to do with powers of two).
Powers of two
Theorem
Theorem
It states that 
Why do we need it?
It is useful is 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 
...n times. 
.
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.
Links
AoPS links
https://artofproblemsolving.com/videos/counting/chapter12/141 https://artofproblemsolving.com/videos/counting/chapter12/140 https://artofproblemsolving.com/videos/counting/chapter12/142 https://artofproblemsolving.com/videos/mathcounts/mc2010/419
Other links
http://jwilson.coe.uga.edu/EMAT6680Su12/Berryman/6690/BerrymanK-Pascals/BerrymanK-Pascals.html https://www.mathsisfun.com/pascals-triangle.html https://www.cut-the-knot.org/arithmetic/combinatorics/PascalTriangleProperties.shtml https://en.wikipedia.org/wiki/Pascal%27s_triangle
