Proof by Strong Induction [Discrete Math Class]

[@jakobr_]

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

[@MathVisualProofs]

Definitely true! But quicker not to go class by class :).

[@jakobr_]

@@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.

[@MathVisualProofs]

@@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. :)

[@doomcake2020]

This was the video that truly clarified strong induction for me, thank you so much!

[@MathVisualProofs]

Glad it was helpful!

[@Tucan_-wj5qo]

godsent thx, not gonna lie made me understand it better then sitting 1 hour at collage lecture

[@epic_editz_x]

These videos should get millions of views

[@MathVisualProofs]

Thanks!

[@supu8599]

Very good 👍. Learned a new thing today

[@MathVisualProofs]

Thanks!

[@rezhannoori2998]

Amazing Video. Thank you for doing this!

[@MathVisualProofs]

Thanks for checking it out.

[@pengin6035]

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?

[@MathVisualProofs]

Nice problems!

[@jakobr_]

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.

[@pengin6035]

@@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

[@jakobr_]

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

[@aubrie3568]

this is an amazing video, thank you!

[@MathVisualProofs]

Glad you liked it!

[@oojivel]

wouldnt the prime factorization proof have infinitely many base cases?

[@MathVisualProofs]

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).

[@oojivel]

@@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.

[@MathVisualProofs]

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.

[@supu8599]

7:06 20+20+9-6

[@MathVisualProofs]

So what are a, b, and c then? ;)

[@supu8599]

@@MathVisualProofs nothing

[@MathVisualProofs]

@@supu8599 hah! Oh I missed the minus sign :) good one

[@supu8599]

@@MathVisualProofs 😤

[@mathdoctor2370]

Can you give me your manim source code via email?

[@MathVisualProofs]

Yes. I can't promise it will be readable :)