Difference between revisions of "Pascal's Triangle and Pythagorean Theorem"
(Created page with "= 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 <m...") |
m (→Introduction to Pascal's Triangle: Spelling mistake: its instead of it's) |
||
Line 37: | Line 37: | ||
Pascal's Triangle is really combinations. It looks something like this if it is depicted as 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{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... | And on and on... | ||
Line 45: | Line 45: | ||
=== Proof === | === 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>. | + | 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>. It's Pascals Identity! Therefore each row looks something like this: |
<math>\binom{n}{0} \binom{n}{1} \binom{n}{2} ... \binom{n}{n}</math> | <math>\binom{n}{0} \binom{n}{1} \binom{n}{2} ... \binom{n}{n}</math> |
Latest revision as of 08:25, 13 February 2020
Contents
Pascal's Identity
Identity
Pascal's Identity states that
for any positive integers and . Here, is the binomial coefficient .
Remember that
Proving it
If then and so the result is pretty clear. So assume . Then
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:
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: . It's Pascals Identity! Therefore each row looks something like this:
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:
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 . Repeatedly using the distributive property, we see that for a term , we must choose of the terms to contribute an to the term, and then each of the other terms of the product must contribute a . Thus, the coefficient of is the number of ways to choose objects from a set of size , or . Extending this to all possible values of from to , we see that , as claimed.
Similarly, the coefficients of will be the entries of the 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
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 ...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.
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:
Hockey stick
For .
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 .
Base Case Let .
.
Inductive Step Suppose, for some , . Then .
Algebraic Proof
It can also be proven algebraically with Pascal's Identity, . Note that
, which is equivalent to the desired result.
Combinatorial Proof 1
Imagine that we are distributing indistinguishable candies to distinguishable children. By a direct application of Balls and Urns, there are ways to do this. Alternatively, we can first give candies to the oldest child so that we are essentially giving candies to kids and again, with Balls and Urns, , which simplifies to the desired result.
Combinatorial Proof 2
We can form a committee of size from a group of people in ways. Now we hand out the numbers to of the people. We can divide this into disjoint cases. In general, in case , , person is on the committee and persons are not on the committee. This can be done in ways. Now we can sum the values of these disjoint cases, getting
See Also
AoPS Wiki
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 made by Colball otherwise known as Colin Friesen
- Pascal's Identity
- Hockey-Stick Identity
- Pascal's Triangle
These are all on AoPS wiki. Look them up.
Now to Pythagorean Theorem.
What is the Pythagorean Theorem?
What is the Pythagorean Theorem?
The Pythagoras Theorem is also referred to as the Pythagorean Theorem Pythagorean Theorem is used to find a side of any right triangle. It is , where and are the legs of the triangle, and is the hypotenuse.
Why is it useful?
To find sides and angles of right triangles. Also, Trigonometry is pointless without it. If you know three angles of a triangle you can use the Pythagorean Theorem to find the sides or the area even if the angles are not right. It is probably the most famous Theorem in all of math!
Can we prove it?
Yes! The are hundreds of proves. I will just show you a few of them. Mathematicians even make a hobby of finding these proves. Even a US president made a published proof! Of, course this was a president in the 1800s because, well, presidents now are not really up to proving something like that. (You know, Trump and the others).
Proofs
Proof 1
We use to denote the area of triangle .
Let be the perpendicular to side from .
Since are similar right triangles, and the areas of similar triangles are proportional to the squares of corresponding side lengths,
.
But since triangle is composed of triangles and , , so . ∎
Proof 2
Consider a circle with center and radius . Since and are perpendicular, is tangent to . Let the line meet at and , as shown in the diagram:
Evidently, and . By considering the power of point with respect to , we see
. ∎
Proof 3
and are squares.
. ∎
Pythagorean Triples
Pythagorean Triples are a group of integers a,b and c in which . These are the first few: (3,4,5) (5,12,13) (7,24,25) (8,15,17)
(9,40,41) (11,60,61) (12,35,37) (13,84,85)
(15,112,113) (16,63,65) (17,144,145) (19,180,181)
(20,21,29) (20,99,101) (21,220,221) (23,264,265)
(24,143,145) (25,312,313) (27,364,365) (28,45,53)
(28,195,197) (29,420,421) (31,480,481) (32,255,257)
(33,56,65) (33,544,545) (35,612,613) (36,77,85)
(36,323,325) (37,684,685)
And on and on... Remember that if then so I did not include 6,8,10 or 10,24,26.
Special Right triangles
45-90-45
Theorem
Say you have a right triangle with angles 45, 45 and 90. Then if (leg) is , then (long side) is
Proof
If this triangle has two equal angles then it has two equal sides. Therefore we can make an equation: . means side and is the hypotenuse. . We proved it!
30-60-90
Theorem
If the angles of a right triangle are 30, 60 and 90, and if the short side is then the long side is and the other leg is .
Proof
The long side is clearly because of the angles that are twice the size, so we can make an equation: . t is the other leg.
We proved it!
Problem 1
Hawick is 15 miles south of Abbotsford, and Kelso is 17 miles east of Abbotsford. What is the distance from Hawick to Kelso?
Solution
Problem 2
A zip line starts on a platform that is 40 feet above the ground. The anchor for the zip line is 198 horizontal feet from the base of the platform. How long is the zip line?
Solution