Proof by Strong Induction [Discrete Math Class]
ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- This video is not like my normal uploads. This is a supplemental video from one of my courses that I made in case students had to quarantine. In this video, we discuss the principle of strong induction: what it is for, why it works, and how to go about using the technique. We compare the technique to standard induction and then we use strong induction to prove that every positive integer has a prime factorization (we do not show uniqueness). We then show that an equilateral triangle can be tiled by n-equilateral triangles (not all congruent) for all n greater than 5. We finish by discussing a famous problem called the Chicken McNugget problem (also known as the Frobenius coin problem).
Note that this video is part of a series kept in a playlist called [Discrete Math Class]:
• Discrete Mathematics C...
If you like this video, please consider subscribing to my channel and let me know in the comments if you'd like to see more like this.
This textbook for the course is the open-source textbook by Oscar Levin:
discrete.openma...
#tiling #equilateraltriangle #triangletiling #chickennuggetproblem #frobeniuscoin #induction #proofbyinduction #stronginduction #primes #primefactors #primefactorization #universalstatements #math #manim #discretemathematics
To learn more about animating with manim, check out:
manim.community
_______________________________________
Background Music:
Undercover Vampire Policeman by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. creativecommon...
Source: chriszabriskie....
Artist: chriszabriskie....
Amazing Video. Thank you for doing this!
Thanks for checking it out.
wouldnt the prime factorization proof have infinitely many base cases?
You can avoid that as I do. You get two cases for n : if it’s prime you’re done; if not, factor. You can also have infinitely many base cases but that’s not as clean because then when you grab an arbitrary integer it is still cases (is it already proved by base case or is it a number that factors).
@@MathVisualProofs I see! Thank you very much, I am having such a hard time applying complete induction for some reason.. I keep getting stuck in the induction step part of the proof where I have to relate the induction hypothesis to the predicate im trying to prove.
it takes some practice. Did you watch the precursor to this video? That cis on standard induction and tries to give some idea about how to go about it.
This was the video that truly clarified strong induction for me, thank you so much!
Glad it was helpful!
43: assume it is possible. 43 is an odd number, so we need an odd number of 9s. 43-9 = 34. The remaining 9s can be paired into 18s, which each can be instead represented by 3*6. Iff we can add 6s and 20s to get 34, 43 is possible. 6a + 20c = 34. Divide by 2. 3a + 10c = 17. Checking mod 3, c=2 or 5 or 8 etc. All of these result in sums greater than 17. Therefore a
Definitely true! But quicker not to go class by class :).
@@MathVisualProofs That is debatable, all six can be done at once with a little generalization.
In my opinion it gets the essence of the proof across a lot more clearly to divide the solution into classes. When you make use of strong induction, we don’t actually need *all* of that information, the info we need follows a certain structure, in that for any integer we *only* need to know whether it worked for exactly the integer six below the one in question.
This is not like the prime factorization example where all we know about a composite number’s nontrivial factors is that those factors are less than it.
@@jakobr_ agreed it is debatable :) the two techniques are logically equivalent but from a pedagogical viewpoint the idea is to talk about remembering one case vs remembering many. Especially when people are first learning the idea of splitting into cases for different induction steps is advanced. Plus things like the chicken nugget problem have non (well not explicit) induction proofs. :)
Very good 👍. Learned a new thing today
Thanks!
godsent thx, not gonna lie made me understand it better then sitting 1 hour at collage lecture
Nice! Here is another challenge using this principle for the ones interested: Show that for all n≥4, there are non-zero rational numbers a_i from i=1 to n such that the sum of the a_i² is equal to 1 while the sum of the a_i is equal to 0.
Bonus question: Prove that we don't find these a_i for n=3
Bonus bonus question: Can you show the first result while only using weak induction and not strong induction?
Nice problems!
Induction step: if there exist a_i from 1 to k-1 where the sum of a_i = 0 and the sum of (a_i)^2 = 1, then set a_k = 0. This changes neither sum, and since zero is rational this is a valid sequence of k rational numbers satisfying the same conditions.
base case: n=4
Assume such a_i exist.
Express the four rational numbers in terms of their least common denominator: b/m, c/m, d/m, e/m. Now b+c+d+e = 0, and b^2 + c^2 + d^2 + e^2 = m^2. All five numbers are integers, and m can be assumed to be positive. It’s easy to see that b = d = 1, c = e = -1, and m=2 satisfy these conditions.
@@jakobr_ Ahhh I again forgot about the non-zero thing... Yeah, assume that none of the a_i are 0, otherwise it's easy... But good catch :D
Bonus: n=3
the n=1 case is impossible because 0≠1.
the n=2 case has one unordered pair of solutions: (2^(-1/2),-2^(-1/2)) which are not rational, this is made clear by graphing the two sums.
The n=3 problem is equivalent to finding positive integers a, b, c, and m such that a + b - c = 0 and a^2 + b^2 + c^2 = m^2. m can be asserted to be positive for obvious reasons. It’s clear that, when none of the rational numbers are zero, they cannot all have the same sign. And if any were zero, there would be solutions for a case where n
These videos should get millions of views
Thanks!
this is an amazing video, thank you!
Glad you liked it!
Can you give me your manim source code via email?
Yes. I can't promise it will be readable :)
7:06 20+20+9-6
So what are a, b, and c then? ;)
@@MathVisualProofs nothing
@@supu8599 hah! Oh I missed the minus sign :) good one
@@MathVisualProofs 😤