8.21 Induction

1.Proposition:

Let \(X\subseteq \N\) be s set

If \(1\in X\)

\(k\in X\Rightarrow k+1\in X\)

Then \(X=\N\)

Proof:

Use contradiction

Suppose \(X\neq \N\), Consider \(S=N\setminus X\)

Then \(S\subseteq \N,~S\neq \emptyset\)

by W.O.P. There is \(k\in S\) , it is first element

Note that \(k\neq 1\) , then \(k-1\in\N\) and \(k-1\notin S\)(Because \(k\) is the first element in \(S\))

\(\Rightarrow k-1\in X\Rightarrow k-1+1\in X \Leftrightarrow k\in X\)

\(\Rightarrow k\in X \wedge k\notin X\) Contradiction

Then \(X=\N\)

‍

2.Reinterpretation of this principle

\(p(m)\) a propositional function with domain \(\N\)

\(X=\{n\in \N|P(n)~is~ture\}\)

Then

If \(P(1)\) is true

\(P(n)\) is true \(\Rightarrow P(n+1)\) is true

Then \(P(n)\) is true . \(\forall m\in \N\)

‍

Example

\(S_n=1+2+3+...+n\)

\(p(n):"S_n=\frac{n(n+1)}{2}"\)

We will prove \(P(n)\) is true . \(\forall n\in \N\)

In other words: \(\sum_{i=1}^{n}i=\frac{n\left(n+1\right)}{2}~~,\forall n\in N\)

We proceed by induction in \(n\): \(P\left(1\right):S_{1}=\frac{1.\left(1+1\right)}{2}\), P(1) is true

Assume \(P(n)\) true, and prove \(P(n+1)\) true

Hypothesis: \(1+2+3+\cdots+n=\frac{n(n+1)}{2}\) for some fixed \(n\)

Need to prove: \(1+2+3+\cdots+n+n+1=\frac{(n+1)(n+2)}{2}\)

\(1+2+3+\cdots+n+n+1=\frac{n(n+1)}{2}+n+1=\frac{n(n+1)+2(n+1)}{2}=\frac{\left(n+1\right)\cdot\left(n+2\right)}{2}\)

Then \(P(n)\Rightarrow P(n+1)\) Contradiction \(P(n)\) true \(\forall n\in \N\)

‍

Example

Prove that \(4^{2n}-1\) is multiple of 15. \(\forall n\in \N\)

To prove this by contradiction we prove two things

\(n=1,4^{2n}-1\) is multiple of 15

Indeed \(4^2-1=16-1=15\) ok

If true for n \(\Rightarrow\) True for n+1

Hypothesis \(4^{2n}-1=15k,k\in \N\)

Claim: \(4^{2(n+1)}-1=15q,q\in \N\)

Note that \(4^{2\left(n+1\right)}-1=4^{2n}\cdot16-1=4^{2n}\left(15+1\right)-1=4^{2n}\times15+4^{2n}-1=4^{2n}\times 15+15\times k,k\in N=15\times \left(4^{2n}+k\right)\) multiple of 15

‍

3.Modified induction

Let \(X\in\N| n_0\in X\),(\(n\geq n_0 \wedge n\in X)\Rightarrow n\in X\Rightarrow n+1\in X,\forall n\geq n_0\)

The propsotional version of this is:

If \(P(n)\) is a propostion such that

\(P(n_0)\) is true
\(\forall n\geq n_0\) \(P(n)\Rightarrow P(n+1)\)

We can get \(P(n)\) is true \(\forall n\geq n_0\)

‍

4.Strong induction

Notation: Consider the proposition for \(n\in \N\),\(n>1\)

\(p(n):\)"n has a prime factor" (prime divisor)

What happens if we try to use induction?

\(P(2)\) true

Try to prove \(P(n)\Rightarrow P(n+1)\)

Problem: Prime factors of n completely unrelated to the prime factors of \(n+1\)

‍

Back to the definitions for STRONG INDUCTION

Let \(X=\{n_0,n_1,n_2,......\}\subseteq \N\)

Let \(S\subseteq X\) such that :

\(n_0\in S\)
\(\forall n\geq n_0,(x\in S:n_0\leq x\leq n)\Rightarrow n+1\in S\Rightarrow S=X\)

Proof

Suppose \(S\neq X\). consider \(S\prime =X\setminus S\), assume \(S\prime \neq \emptyset\)

By W.O.P. \(\Rightarrow n_k\in S\prime(0\leq k)\), its first element.

Hence \(n_{k}-1\notin S\prime\Rightarrow n_{k}-1\in S(Since~ \forall n\geq n_0,(x\in S:n_0\leq x\leq n_k-1) ~)\Rightarrow n_{k}\in S\)

Contradiction!

‍

In the language of propositional functions:

Let \(p(n)\) be a prop.funct. with domain \(\{n_0,n_1,n_2,......\}\)

If

\(P(n_0)\) is true
\(\forall n\geq n_0\) \((P(x)~true~~\forall n_0\leq x\leq n)\Rightarrow P(n+1)\)

Then P(n) is true \(\forall n\geq n_0\)

‍

5.Back to the motivating problem

\(p(n):\)"\(n\) has a prime factor" (\(n\) is a product of primes)(\(n>2\))

\(p(2)\) true

Let's prove that for any \(n\in\N\)

\((p(2)\wedge p(3)\wedge \cdots \wedge p(n-1))\Rightarrow p(n).\)

Hypothesis is that \(\forall m<n\), \(m\) is a prime factor

Note take \(n\in \N\)

Case 1:\(n\) is a prime \(\Rightarrow\) \(p(n)\) is true

Case 2:\(n\) is not prime. This means that

\(n=m_1*m_2\) \(m_1\neq 1,m_2\neq1\)

Note that \(m_1<n\), \(m_2<n\). Then, the inductive hypothesis says that \(m_1\), \(m_2\) has a prime factor.

\(n\) has a prime factor

‍

6.Integer numbers (Axioms, divisibility, integer division, g.c.d)

\(\Z=\{....-3,-2,-1,0,1,2,3....\}\)

\(\Z=-\N\cup \{0\}\cup \N\)

\(+:\Z_{\times}\Z\rightarrow \Z~~~~~~\cdot :\Z_{\times}\Z\rightarrow \Z\)

(a,b)\(\rightarrow\)a+b (a,b)\(\rightarrow\)a\(\cdot\)b

Axiom: \(a,b,c\in \Z\)

\(a+(b+c)=(a+b)+c\) \((a*b)*c=a*(b*c)\)
\(a+b=b+a\) \(a*b=b*a\)
\(a*(b+c)=a*b+a*c\)
Identity elements

\(a+0=a\) \(a*1=a\)
Additive inverse. For every \(a\in\Z\), \(\exists\) unique element that we call \(-a\) such that \(a+(-a)=0\)
Cancellation property

\(a,b,c\in\Z\), \(a\neq 0\)

\(a*b=a*c\Rightarrow b=c\)

Theorem: Prove that \(a\in\Z\), then \(a*0=0\)

\(a\times 0\in \Z\), \(a\times 0=a\times\left(0+0\right)=a\times0+a\times0\)

Hence \(a\times 0=a\times0+a\times0\)

Since \(a\times 0\in \Z\), there exist an inverse called \(-(a\times 0)\)

\(a\times 0+-\left(a\times0\right)=a\times0+a\times0+-\left(a\times0\right)\)

\(0=a\times 0+0=a\times0\)

\(0=a\times0\)

‍

Theorem: Prove that for \(a\in\Z\), \(-a=(-1)*a\)

We need to prove that \((-1)*a\) behaves like the inverse of \(a\)

\(a+\left(-1\right)\times a=1\times a+\left(-1\right)\times a=a\times \left(1+\left(-1\right)\right)=a\times 0=0\)

Then \((-1)\times a\) is the inverse of \(a\): \((-1)\times a=-a\)

‍

Well ordering and induction in \(\Z\)

Let \(X\subseteq \Z\). We say that \(X\) is a bounded from below

If \(\exists b\in \Z|b\leq x,\forall x\in X\)

\(N\subseteq \Z\) is bounded from below

\(\{...,-3,-2,-1,0,1,2,3,...\}\subset \Z\) is bounded from below

W.O.P: Any non-empty set \(X\subseteq \Z\) that is bounded from below has a first element

Induction in \(\Z\): Let \(p(n)\) be a propositional function with domain \(\Z\)

If

\(P(n_0)\) is true for some \(n_0\in \Z\)
\(\forall n\geq n_{0},P\left(n\right)\Rightarrow P\left(n+1\right)\)

Then \(P(n)\) is true, \(\forall n\geq n_0\)