Chandan Singh | Proofs


view markdown


  • induction
    • must already know formula
    • doesn’t give intuition
    • there are uncomputable functions e.g. Halting Problem, 3x+1 problem
  • non-existence proofs
    • must cover all possible scenarios, harder than existence


  • Biggest primes, the twins
  • Infinite twin primes – guy working at subway
  • Different infinites – people driven crazy
  • Four-Color problem – Computer aided proof in 1977, basically checks cases
  • Bruower’s Fixed Point Theorem
  • Fermat’s Last Theorem – Pythagorean thm untrue for anything bigger than squared
    • Pf in 1995
  • Godel’s Thm: there are unprovable statements
  • Pigeonhole Principle
    • Claim: Consider a 10 foot by 10 foot square room. Let every point on the floor of the room be colored either red or blue. Then there exists somewhere on the floor two points of the same color that are exactly one foot apart.
    • Proof: Consider an equilateral triangle on the floor of the room with side lengths equal to one foot. As every point is either red or blue, two vertices of the triangle must have the same color, satisfying the claim.
    • There must be 2 people in London with the same amount of hairs on their head