Proof by Strong Induction [Discrete Math Class]

Поділитися
Вставка
  • Опубліковано 26 лис 2024

КОМЕНТАРІ • 31

  • @jakobr_
    @jakobr_ 2 роки тому +4

    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
      @MathVisualProofs  2 роки тому +1

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

    • @jakobr_
      @jakobr_ 2 роки тому +1

      @@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
      @MathVisualProofs  2 роки тому +1

      @@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
    @doomcake2020 2 місяці тому +2

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

  • @epic_editz_x
    @epic_editz_x 8 місяців тому +2

    These videos should get millions of views

  • @rezhannoori2998
    @rezhannoori2998 2 місяці тому +2

    Amazing Video. Thank you for doing this!

  • @supu8599
    @supu8599 2 роки тому +4

    Very good 👍. Learned a new thing today

  • @Tucan_-wj5qo
    @Tucan_-wj5qo Рік тому +1

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

  • @pengin6035
    @pengin6035 2 роки тому +2

    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
      @MathVisualProofs  2 роки тому +1

      Nice problems!

    • @jakobr_
      @jakobr_ 2 роки тому +1

      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
      @pengin6035 2 роки тому

      @@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_
      @jakobr_ 2 роки тому +1

      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
    @aubrie3568 8 місяців тому +1

    this is an amazing video, thank you!

  • @oojivel
    @oojivel Місяць тому +2

    wouldnt the prime factorization proof have infinitely many base cases?

    • @MathVisualProofs
      @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
      @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
      @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
    @supu8599 2 роки тому +1

    7:06 20+20+9-6

    • @MathVisualProofs
      @MathVisualProofs  2 роки тому

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

    • @supu8599
      @supu8599 2 роки тому +1

      @@MathVisualProofs nothing

    • @MathVisualProofs
      @MathVisualProofs  2 роки тому +1

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

    • @supu8599
      @supu8599 2 роки тому

      @@MathVisualProofs 😤

  • @mathdoctor2370
    @mathdoctor2370 2 роки тому

    Can you give me your manim source code via email?