CSCE 222 Lecture 17

« previous | Friday, March 4, 2011 | next »

Mathematical Induction

Let $P(n)$ be a prediate with domain of natural numbers (not including zero). Suppose that we want to show $\forall xP(x)$ is true:

${\begin{array}{l}P(1)\\P(n)\rightarrow P(n+1)\\\hline \therefore \forall xP(x)\ {\mbox{is true}}\end{array}}$

Note: Induction is just an infinite amount of modus ponens arguments

In general, we always prove $P(x_{0})$, where $x_{0}$ is our starting premise. For example, if we wanted to prove something was true for all natural numbers (including zero), we would first have to show $P(0)$ is true, then show $\forall x(P(x)\rightarrow P(x+1))$.

Example 1

Show that $P(k)=\sum _{m=1}^{k}(2m-1)=k^{2}$ is true.

$P(1)$ is true: $2\cdot 1-1=1^{2}$

Assume that $P(k)$ is true. is $P(k+1)$ true?

${\begin{aligned}1+3+\ldots +2k-1&=k^{2}&P(k)\ {\mbox{hypothesis}}\\1+3+\ldots +2k-1+2(k+1)-1&=(k+1)^{2}&P(k+1)\ {\mbox{implication}}\\1+3+\ldots +2k-1+2k+1&=k^{2}+2k+1&{\mbox{expand}}\ (k+1)^{2}\\1+3+\ldots +2k-1&=k^{2}&{\mbox{subtract}}\ 2k+1\ {\mbox{to get hypothesis}}\end{aligned}}$

Example 2

If you make $n$ straight cuts across a pizza, then you divide it into at most ${\frac {n(n+1)}{2}}+1$ pieces.

If we make a single cut, then we divide the pizza into 2 pieces, which holds true.

Suppose that for $n$ cuts, the claim holds true. The next cut will create the largest possible number of pizza pieces iff we cut through all previous lines and avoid intersections. An additional piece is created every time we cross a line, creating at most $n+1$ additional pieces.

${\frac {n(n+1)}{2}}+1+n+1={\frac {n^{2}+n+2n+2}{2}}+1={\frac {(n+1)(n+2)}{2}}+1=P(n+1)$

Therefore, the claim holds by induction.

Direct Proof

An integer $l$ is called even iff there exists an integer $l'$ such that $l=2\cdot l'$.

Lemma: Prove that the sum of two even integers is an even integer.

Proof: Suppose that $x$ and $y$ are two even integers. Then $x=2\cdot x'$ and $y=2\cdot y'$. Therefore $x+y=2\cdot x'+2\cdot y'=2(x'+y')$ is an even number.

Proof by Contradiction

Lemma: Prove that there are infinitely many prime numbers.

Proof: By contradiction, suppose there is a finite number of prime numbers $p_{1}$ to $p_{n}$. However, $q=1+\prod _{k=1}^{n}p_{k}$ is not divisible by any prime numbers (will always have a remainder of 1):

$q\equiv 1\mod p_{k}\quad 1\leq k\leq n$

Therefore, $q$ must be a prime number that is not in our finite list of prime numbers, which contradicts our assumption of a finite number of primes.