View source for FA18:Lecture 13 strong induction and euclidean division

We introduced [[strong induction]] and used it to complete our proof that [[:Claim:Every natural number has a prime factorization|Every natural number is a product of primes]].  We then started our discussion of [[:Category:number theory|number theory]] with the [[euclidean division algorithm]].

* [[File:fa18-lec13-board.pdf]]
* [http://www.cs.cornell.edu/courses/cs2800/2017sp/lectures/lec29-division.html Last semester]

= Notation: sequences =

In this lecture, we will use a bit of shorthand for representing (finite) [[sequence]]s:

{{:Sequence notation}}

= Strong induction =

In the [[FA18:Lecture 12 induction|last lecture]], we [[:Proof:Every natural number has a prime factorization (weak induction; doesn't work)|tried to prove]] that [[every]] [[natural number]] has a [[prime factorization]].

We begin this lecture by showing how to modify that proof by [[strengthening the inductive hypothesis]], and then we introduce the general technique of [[strong induction]].

== Strengthing the inductive hypothesis ==

{{:Strengthening the inductive hypothesis}}

For example,
{{:Proof:Every natural number has a prime factorization (strengthened induction hypothesis)}}

== Strong induction ==

[[Strengthening the inductive hypothesis]] in this way (from <math>P(n)</math> to <math>∀k ≤ n, P(n)</math>) is so common that it has some specialized terminology: we refer to such proofs as proofs by [[strong induction]]:


{{:Strong induction}}

{{:Proof:Every natural number has a prime factorization}}

= Euclidean division =

With these basic techniques ([[weak induction]] and [[strong induction]]) under our belt,
we can begin the study of [[:Category:number theory|number theory]].

{{:Number theory}}

{{:Euclidean division algorithm}}

== Proofs and algorithms ==

{{:Algorithm}}

== Uniqueness of euclidean division ==

{{:Proof:The quotient and remainder are unique}}