Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Power's of 2 in pascal's triangle"
 
(7 intermediate revisions by the same user not shown)
Line 31: Line 31:
 
               1+3+3+1  =8
 
               1+3+3+1  =8
 
             1+4+6+4+1 =16
 
             1+4+6+4+1 =16
−
These are powers of two. Let's prove it true. (Note: There are dozens of more patterns but it would have nothing to do with powers of two).
+
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 =
 
= Powers of two =
Line 39: Line 39:
 
=== Theorem ===
 
=== Theorem ===
  
−
It states that <math>\binom{n}{0}+\binom{n}{1}+...+{n}{n}</math>.
+
It states that <math>\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n</math>
  
 
=== Why do we need it? ===
 
=== Why do we need it? ===
Line 50: Line 50:
 
=== Subset 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)...n times. </math>2^n$.
+
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 ===
 
=== 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.
+
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

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 

                           $\binom{0}{0}$
                $\binom{1}{0}$                  $\binom{1}{1}$
   $\binom{2}{0}$                     $\binom{2}{1}$                $\binom{2}{2}$

And on and on... Remember that $\binom{n}{r}=\frac{n!}{k!(n-k)!}$ where $n \ge r$.

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 $\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=2^n$

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 $(2)(2)(2)(2)$...n times. $2^n$.

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Power%27s_of_2_in_pascal%27s_triangle&oldid=106434"