Using induction spoils the line counting proof. Might as well show (1+2+...+(n+1))^2 - (1+2+...+n)^2 = (n+1)^3 if you're gonna take the induction approach.
The example at 9:40 is not correct since according to the rules with n=2 we should always have a triangle (since all graphs in sets A and B are always complete graphs).
@@penfelyn Sure. By induction you can show that there are 1+2^3+...+n^3 rectangles in a nXn square. Another way to count the rectangles is this: Each rectangle in the square is uniquely determined by choosing two edges/lines at the bottom of the square and two at the side. There are n+1 lines on each side, so there are Ncr(n+1,2)^2 rectangles. And Ncr(n+1,2)=1+...+n
@@aleksandervadla9881 Not just by induction If you want an intuitive way, In an nxn square, the number of rectangles with lower side length equal to (n-k+1) is k^3 And for every rectangle, the lower side length is unique and thus there are no duplicate counts
I was discussing this with my son when it occurred to me that this is related to the Diophantine equation n^3 + 1 = (n+1)^2, which has only the two integer solutions { -1, 2 }. It took me until just now to realize that the solution n=2 is a direct consequence of this identity.
nice video! but in 9:40, there could not exist that ANY two lines parallel, even if it's from the same set. If n=2 and there exist two lines from A which are parellel, we should need 4th point. good proof tho.
I stumbled upon this identity in high school when I noticed that the 9th triangle number (45) and the 10th triangle number (55) square to 2,025 and 3,025 respectively. Their difference was suspiciously 1,000, which is 10³. I wanted to see if I could prove the formula without induction and came up with this: Define S(n) = 1 + 2 + ... + n = (n+1)n/2 n³ = (1/4)*(4n³) = (1/4)*([2n³] - [-2n³]) = (1/4)*[(n⁴ + 2n³ + n²) - (n⁴ - 2n³ + n²)] = (n²/4)*[(n² + 2n + 1) - (n² - 2n + 1)] = (n²/4)*[(n+1)² - (n-1)²] = [(n+1)²n²/4] - [n²(n-1)²/4] = S(n)² - S(n-1)² From this, we see: n³ + (n-1)³ = [S(n)² - S(n-1)²] + [S(n-1)² - S(n-2)²] = S(n)² - S(n-2)² n³ + (n-1)³ + (n-2)³ = [S(n)² - S(n-1)²] + [S(n-1)² - S(n-2)²] + [S(n-2)² - S(n-3)²] = S(n)² - S(n-3)² ... n³ + (n-1)³ + ... + 1³ = S(n)² - S(0)² = S(n)²
There's a nice geometric illustration of the (1+2+...+n)^2 =1^3 + 2^3 + ... + n^3 identity Tile a square courtyard of side 1 + 2 + 3 + ... + n Start with a 1x1 tile at the top right corner Fit 2 2x2 tiles right and below the tile just laid. There's a 1x1 overlap, but also a 1x1 gap. Chisel out the overlap to fill the gap (do this with every even number) Add 3 3x3 tiles right and below the tiles just laid Continue tiling, to complete the tiling with n nxn tiles Then the area tiled is (1+2+...+n)^2 and also 1x(1x1) + 2x(2x2) + 3x(3x3) + ,,, + nx(nxn) = 1^3 + 2^3 + ... + n^3 Draw pictures!
Hmmm seems so complicated compared to "just working out the series math". The sum of (1, 2, 3, ... n) is the well known n(n+1) / 2. Square that, and we get n²(n+1)²/2² which expands to (n⁴ + 2n³ + n²)/4 By itself, it doesn't imply much. But then just taking difference of the next (k+1) and 'this' (k) form gives the following (k+1)⁴ + 2(k+1)³ + (k+1)² - (k⁴ + 2k³ + k²) ... which expands to {[k⁴ + 4k³ + 6k² + 4k + 1] + 2[k³ + 3k² + 3k + 1] + [k² + 2k + 1] - k⁴ - 2k³ - k² }/4 which consolidates to [ 4k³ + 12k² + 12k + 4 ] / 4 which loses the divide-by-4 to be k³ + 3k² + 3k + 1, which has the fairly obvious polynomial form (k + 1)³ Well, that means that the (k+1)th term of the original summation-squared is the kth term PLUS the (k+1)³ value. This extends all the way to k=0, as the summation is 0. ERGO ... proven. Didn't need intersections of sets, or combinatorics, or anything else. Just a bit of whats-the-next-term math and good old algebra. See?
I do not see how these points make sure that the lines from A do not intersect the lines from B at one of the intersection points of A: a = { (1,1}, (2,2), (1,-1). (2,-2) } b = ( (10,0), (-10,0) .... } There is a set of lines in A that intersect at (0,0), and there is a a line in b that intersect at (0,0) which reduces the intersections by one.Unless we are allowed to count it double (like how we count roots)
Your proof is indeed great and needs a lot of Math. We learnt in school the formula for the sum of cubes of natural nos 1,2,.... n= ((n+1)/2)^2, which is the SQUARE of the sum of natural nos 1,2,3,...n. Of course the RHS is easily derived using the difference of cubes Identity (k+1)^3-k^3, and writing down the series setting k=0,1,2,....n for the terms on the LHS. Pretty simple and straightforward isn't it, Mile?
i saw this and wondered if the said identity has its own name, similar to Plato's Law. it seems on the left the identity is calculating the square of the sum of nodes on an n layer pascal's triangle. with some effort i found the name of the formula: Nicomachus' Theorem.
Before starting the video, I did the proof by induction just using basic algebra using (1+2+...+n) = n(n+1)/2. It's always interesting to see the corresponding geometric mechanisms behind the proof.
The main problem with induction is that you already need to know the result of the summation to make a proof. While with other approaches you can come up with the result directly at the same time proving it.
@PunkSage That's true. But induction is often used after identifying a pattern in the first view values of n. Like noticing that the sum of the first few cubes is always a square.
Of course, there are quicker and easier ways of proving the (1+2+...+n)^2 =1^3 + 2^3 + ... + n^3 result, but the proof that Penn presents here is most ingenious, and the approach is as unexpected as the result itself* Take a bow Ms Turner *A sub-theme for the channel: surprising proofs of surprising results?
What general position is depends on the problem. If you're doing a Delaunay triangulation, general position means no three points on a line and no four on a circle.
09:00 how do we know that the intersections are unique? I don't see that that follows from pur assumptions on the r.h.s. of the board. We just know that all lines are unique, and that all pairs of lines with one in A and one in B intersects. But not that those intersections are all unique. Am I missing something? There seems to be nothing ng to say that we need to have unique intersections, just that we count whenenever they intersects, but it bothers me. Anyways, excellent video!
11:00 It seems like you calculated the maximum number of possible intersections on lines in A with lines in B, but in the setup in the video it's possible that the actual number of intersections is less because you could have two pairs of lines from A and B sharing the same intersection point.
@@w.nickel2792 Sure, you could do that, it’s just not what he said in the video. The whole reason he had no three points be colinear for example was to avoid this type of issue. You could do this proof without that colinear restriction by saying if the lines are colinear they “still count as just one intersection”, after all. Heck, you don’t even need “lines” at all, just pairs of two distinct elements each from sets A and B, why use lines at all? It’s just not what he actually did though.
Didn't we count some intersection twice in induction step proof? like a0a_(k+1) and b0b_{k+1} intersection was count first when we were working with a_ia_(k+1) type of pairs and second time when we were working with b_ib_(k+1) type ?
It is possible with the axiom of choice. List the elements of R^3 \ {0} in a well-ordered sequence of length c, the smallest uncountable ordinal. Go through the elements in order, choosing a line passing through each, skipping any x covered by previously chosen lines. At every stage we always have one line to choose because only countably many directions have been blocked.
"No line defined by points in A is parallel to a line defined by points in B." Do we already know that this is always possible, given that the number of points gets arbitrarily large?
This will hold for all p & q when n=1. Consider n=2. The equation becomes (1+2)^p=(1^q+2^q) => 3^p=1+2^q. This is true for p=2, q=3, that is 3^2=1+2^3. That is, there is a power of 3 that is one more than a power of 2. This is a necessary but NOT sufficient condition for the more general case. I speculate, but cannot prove, that this condition only holds for p=2, q=3. So, I speculate that there are no more cases.
Hello, Professor Pann. We recently followed you (learning for Fermat's last theorem). We love your videos. This induction proof is very interesting, but I think there is a mistake at 11 minutes. Set A should be three lines connected by three points, and set B is the same. In addition, my daughter also has a very interesting proof of the sum of cubes of n natural numbers: ua-cam.com/video/0lp1b5BcqIU/v-deo.html
Can't you use the formulas for 1 + 2 + 3 + ... + n = (n+1)(n/2) and 1^3 +2^3 + 3^3 + ... + n^3 = (n+1)^2 * n^2 / 4 and see that it is that? And you can prove those 2 formulas.
@@maxhagenauer24 You are completely missing the point. This video is about a novel and distinct proof that links Michael's favorite identity to something different and unexpected than the normal formula approach.
@bsmith6276 Yes I get that, I was simply asking wheather the method of deriving the formulas works but shoryaprakash8945 said you don't have to do it the way of proving the formulas which sounded very odd. It sounded as if he was implying the way in the video was easier and faster which I disagreed with. I don't know how you got that I am not understanding the point of the video.
Using induction spoils the line counting proof. Might as well show (1+2+...+(n+1))^2 - (1+2+...+n)^2 = (n+1)^3 if you're gonna take the induction approach.
The example at 9:40 is not correct since according to the rules with n=2 we should always have a triangle (since all graphs in sets A and B are always complete graphs).
Another nice way to show this identity is to count the number of rectangles in a nxn square in two different ways!
I I don't think I get it.. can you please go a little further into it?
@@penfelyn Sure. By induction you can show that there are 1+2^3+...+n^3 rectangles in a nXn square. Another way to count the rectangles is this: Each rectangle in the square is uniquely determined by choosing two edges/lines at the bottom of the square and two at the side. There are n+1 lines on each side, so there are Ncr(n+1,2)^2 rectangles. And Ncr(n+1,2)=1+...+n
@@aleksandervadla9881
Not just by induction
If you want an intuitive way,
In an nxn square, the number of rectangles with lower side length equal to (n-k+1) is k^3
And for every rectangle, the lower side length is unique and thus there are no duplicate counts
I was discussing this with my son when it occurred to me that this is related to the Diophantine equation n^3 + 1 = (n+1)^2, which has only the two integer solutions { -1, 2 }. It took me until just now to realize that the solution n=2 is a direct consequence of this identity.
nice video! but in 9:40, there could not exist that ANY two lines parallel, even if it's from the same set. If n=2 and there exist two lines from A which are parellel, we should need 4th point. good proof tho.
Been struggling with that statement too
I stumbled upon this identity in high school when I noticed that the 9th triangle number (45) and the 10th triangle number (55) square to 2,025 and 3,025 respectively. Their difference was suspiciously 1,000, which is 10³. I wanted to see if I could prove the formula without induction and came up with this:
Define S(n) = 1 + 2 + ... + n = (n+1)n/2
n³ = (1/4)*(4n³) = (1/4)*([2n³] - [-2n³]) = (1/4)*[(n⁴ + 2n³ + n²) - (n⁴ - 2n³ + n²)] = (n²/4)*[(n² + 2n + 1) - (n² - 2n + 1)] = (n²/4)*[(n+1)² - (n-1)²] = [(n+1)²n²/4] - [n²(n-1)²/4] = S(n)² - S(n-1)²
From this, we see:
n³ + (n-1)³ = [S(n)² - S(n-1)²] + [S(n-1)² - S(n-2)²] = S(n)² - S(n-2)²
n³ + (n-1)³ + (n-2)³ = [S(n)² - S(n-1)²] + [S(n-1)² - S(n-2)²] + [S(n-2)² - S(n-3)²] = S(n)² - S(n-3)²
...
n³ + (n-1)³ + ... + 1³ = S(n)² - S(0)² = S(n)²
2025 = 45^2 = (T9)^2= (T(3^2))^2 = (T((T2)^2))^2
Tell that to your friends on New Year's!
Very nice
12:03 This just in: 1^2 = 3^2
This is a fun one, thank you
One of my favourite identity too, expecially the Liouville generalization
There's a nice geometric illustration of the (1+2+...+n)^2 =1^3 + 2^3 + ... + n^3 identity
Tile a square courtyard of side 1 + 2 + 3 + ... + n
Start with a 1x1 tile at the top right corner
Fit 2 2x2 tiles right and below the tile just laid. There's a 1x1 overlap, but also a 1x1 gap. Chisel out the overlap to fill the gap (do this with every even number)
Add 3 3x3 tiles right and below the tiles just laid
Continue tiling, to complete the tiling with n nxn tiles
Then the area tiled is (1+2+...+n)^2 and also 1x(1x1) + 2x(2x2) + 3x(3x3) + ,,, + nx(nxn) = 1^3 + 2^3 + ... + n^3
Draw pictures!
Hmmm seems so complicated compared to "just working out the series math". The sum of (1, 2, 3, ... n) is the well known n(n+1) / 2. Square that, and we get n²(n+1)²/2² which expands to (n⁴ + 2n³ + n²)/4
By itself, it doesn't imply much. But then just taking difference of the next (k+1) and 'this' (k) form gives the following
(k+1)⁴ + 2(k+1)³ + (k+1)² - (k⁴ + 2k³ + k²) ... which expands to
{[k⁴ + 4k³ + 6k² + 4k + 1] + 2[k³ + 3k² + 3k + 1] + [k² + 2k + 1] - k⁴ - 2k³ - k² }/4 which consolidates to
[ 4k³ + 12k² + 12k + 4 ] / 4 which loses the divide-by-4 to be
k³ + 3k² + 3k + 1, which has the fairly obvious polynomial form
(k + 1)³
Well, that means that the (k+1)th term of the original summation-squared is the kth term PLUS the (k+1)³ value. This extends all the way to k=0, as the summation is 0. ERGO ... proven. Didn't need intersections of sets, or combinatorics, or anything else. Just a bit of whats-the-next-term math and good old algebra.
See?
Hi,
1:40 : "and that's a good place to stop" back.
19:25
I do not see how these points make sure that the lines from A do not intersect the lines from B at one of the intersection points of A:
a = { (1,1}, (2,2), (1,-1). (2,-2) }
b = ( (10,0), (-10,0) .... }
There is a set of lines in A that intersect at (0,0), and there is a a line in b that intersect at (0,0) which reduces the intersections by one.Unless we are allowed to count it double (like how we count roots)
Your proof is indeed great and needs a lot of Math.
We learnt in school the formula for the sum of cubes of natural nos 1,2,.... n= ((n+1)/2)^2, which is the SQUARE of the sum of natural nos 1,2,3,...n.
Of course the RHS is easily derived using the difference of cubes Identity (k+1)^3-k^3, and writing down the series setting k=0,1,2,....n for the terms on the LHS. Pretty simple and straightforward isn't it, Mile?
i saw this and wondered if the said identity has its own name, similar to Plato's Law.
it seems on the left the identity is calculating the square of the sum of nodes on an n layer pascal's triangle. with some effort i found the name of the formula: Nicomachus' Theorem.
Before starting the video, I did the proof by induction just using basic algebra using (1+2+...+n) = n(n+1)/2. It's always interesting to see the corresponding geometric mechanisms behind the proof.
The main problem with induction is that you already need to know the result of the summation to make a proof. While with other approaches you can come up with the result directly at the same time proving it.
@PunkSage That's true. But induction is often used after identifying a pattern in the first view values of n. Like noticing that the sum of the first few cubes is always a square.
Nice! This identity is also known as Nicomachus' Theorem
I actually discovered this myself in high school, and discovered how to prove it myself in college
Of course, there are quicker and easier ways of proving the (1+2+...+n)^2 =1^3 + 2^3 + ... + n^3 result, but the proof that Penn presents here is most ingenious, and the approach is as unexpected as the result itself* Take a bow Ms Turner
*A sub-theme for the channel: surprising proofs of surprising results?
What general position is depends on the problem. If you're doing a Delaunay triangulation, general position means no three points on a line and no four on a circle.
09:00 how do we know that the intersections are unique? I don't see that that follows from pur assumptions on the r.h.s. of the board.
We just know that all lines are unique, and that all pairs of lines with one in A and one in B intersects. But not that those intersections are all unique. Am I missing something?
There seems to be nothing ng to say that we need to have unique intersections, just that we count whenenever they intersects, but it bothers me.
Anyways, excellent video!
I think non-unique intersections just count multiple times
11:00 It seems like you calculated the maximum number of possible intersections on lines in A with lines in B, but in the setup in the video it's possible that the actual number of intersections is less because you could have two pairs of lines from A and B sharing the same intersection point.
Right. But you can count intersection points that arise from different pairs of lines with the appropriate multiplicities.
@@w.nickel2792 Sure, you could do that, it’s just not what he said in the video. The whole reason he had no three points be colinear for example was to avoid this type of issue. You could do this proof without that colinear restriction by saying if the lines are colinear they “still count as just one intersection”, after all. Heck, you don’t even need “lines” at all, just pairs of two distinct elements each from sets A and B, why use lines at all? It’s just not what he actually did though.
@@BodyknockI agree.
Looks way overcomplicated to me. Couple lines of induction:
prev = n^2(n+1)^2 = n^2(n^2+2n+1) = n^4+2n^3+n^2
next = ((n+1)(n+2))^2 = (n^2+3n+2)(n^2+3n+2) = n^4+3n^3+2n^2+3n^3+9n^2+6n+2n^2+6n+4 = n^4+6n^3+13n^2+12n+4 =
prev + 4n^3+12n^2+12n+4 = prev + 4(n+1)^3 q.e.d.
I can't help but feel like the geometric aspect of this proof is a bit superficial.
Didn't we count some intersection twice in induction step proof? like a0a_(k+1) and b0b_{k+1} intersection was count first when we were working with a_ia_(k+1) type of pairs and second time when we were working with b_ib_(k+1) type ?
Q: let X=R^3\{O}, the complement of a point O belong to R^3. then X can be partitioned into Euclidean lines.
sir kindly make video on this Q
That sounds suspiciously as if you would like him to make your homework for you.
It is possible with the axiom of choice. List the elements of R^3 \ {0} in a well-ordered sequence of length c, the smallest uncountable ordinal. Go through the elements in order, choosing a line passing through each, skipping any x covered by previously chosen lines. At every stage we always have one line to choose because only countably many directions have been blocked.
"No line defined by points in A is parallel to a line defined by points in B."
Do we already know that this is always possible, given that the number of points gets arbitrarily large?
Why not just prove this by induction?
Here is a nice question for what given p and q does the
(1+2+... +n) ^p = (1^q+2^q+....n^q) holds for all n in N
This will hold for all p & q when n=1.
Consider n=2. The equation becomes (1+2)^p=(1^q+2^q) => 3^p=1+2^q. This is true for p=2, q=3, that is 3^2=1+2^3.
That is, there is a power of 3 that is one more than a power of 2. This is a necessary but NOT sufficient condition for the more general case. I speculate, but cannot prove, that this condition only holds for p=2, q=3. So, I speculate that there are no more cases.
@@robertpearce83943^p-2^q=1 has only one natural solution with p,q>1, that's Mihailescu's theorem (aka Catalan's conjecture).
In the more general problem where p, q can be any real numbers, no new solutions. I have a nice proof, remind me later if you want it.
Why don't you use mathematical induction?
Too easy and less direct. Typically when you evaluate the result of summation we won't have answer you want to prove with induction.
@@PunkSage I prefer to use the least complicated proof to have time to work with harder problems. ;-)
your favorite identity is called nicomachus' theorem. i found that in a few minutes.
said to inspire the philosopher who coined the term, "music of the spheres."
Hello, Professor Pann. We recently followed you (learning for Fermat's last theorem). We love your videos.
This induction proof is very interesting, but I think there is a mistake at 11 minutes. Set A should be three lines connected by three points, and set B is the same.
In addition, my daughter also has a very interesting proof of the sum of cubes of n natural numbers: ua-cam.com/video/0lp1b5BcqIU/v-deo.html
I find it weird that anyone would even _look_ for an alternate proof to what looks like a basic induction problem
Remember when he solved it with genfuncs?
Link?
@@metalsonic8859 The video is called "OVERKILL | My favorite equation".
Can't you use the formulas for 1 + 2 + 3 + ... + n = (n+1)(n/2) and 1^3 +2^3 + 3^3 + ... + n^3 = (n+1)^2 * n^2 / 4 and see that it is that? And you can prove those 2 formulas.
Yes, you can but you don't have to.
@shoryaprakash8945 You also "don't have to" do the method he did, because I think proving each formula is easier and faster than what he did.
@@maxhagenauer24 You are completely missing the point. This video is about a novel and distinct proof that links Michael's favorite identity to something different and unexpected than the normal formula approach.
@bsmith6276 Yes I get that, I was simply asking wheather the method of deriving the formulas works but shoryaprakash8945 said you don't have to do it the way of proving the formulas which sounded very odd. It sounded as if he was implying the way in the video was easier and faster which I disagreed with. I don't know how you got that I am not understanding the point of the video.