MATH 409 Lecture 5

« previous | Tuesday, September 10, 2013 | next »

Lecture Slides

Inductive Definition

Now we can use induction to define structures recursively. For example,

• The power ${\displaystyle a^{n}}$ of a number is ${\displaystyle a^{n}=a^{n-1}\,a}$, where ${\displaystyle a^{0}=1}$.
• Factorial ${\displaystyle n!}$ is ${\displaystyle n!=(n-1)!\,n}$, where ${\displaystyle 0!=1}$.
• Fibonacci numbers: ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$, where ${\displaystyle F_{1}=F_{2}=1}$.

Binomial Coefficients

For any integers ${\displaystyle 0\leq k\leq n}$, we define the binomial coefficient ${\displaystyle {\binom {n}{k}}}$ (${\displaystyle n}$ choose ${\displaystyle k}$) by

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\,\!}$

If ${\displaystyle k>0}$, then

${\displaystyle {\binom {n}{k}}={\frac {n\,(n-1)\dots (n-k+1)}{1\cdot 2\dots k}}\,\!}$

"${\displaystyle n}$ choose ${\displaystyle k}$" refers to the fact that ${\displaystyle {\binom {n}{k}}}$ is the number of all ${\displaystyle k}$-element subsets of an ${\displaystyle n}$-element set.

${\displaystyle {\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}}$

Proof.

{\displaystyle {\begin{aligned}{\binom {n}{k-1}}+{\binom {n}{k}}&={\frac {n!}{(k-1)!\,(n-k+1)!}}+{\frac {n!}{k!\,(n-k)!}}\\&={\frac {n!}{(k-1)!\,(n-k)!}}\,\left({\frac {1}{n-k+1}}+{\frac {1}{k}}\right)\\&={\frac {n!}{(k-1)!\,(n-k)!}}\cdot {\frac {n+1}{k\,(n-k+1)}}\\&={\frac {(n+1)!}{k!\,(n-k+1)!}}\\&={\binom {n+1}{k}}\end{aligned}}}

quod erat demonstrandum

Pascal's Triangle

The lemma formula above allows us to compute coefficients recursively. The results are usually formatted in a triangular array called Pascal's Triangle, where ${\displaystyle {\binom {n}{k}}}$ is the ${\displaystyle k}$th number in the ${\displaystyle n}$th row of the triangle. (numbering starts from 0)

                1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1


Binomial Expansion

Theorem. For any ${\displaystyle a,b\in \mathbb {R} }$ and ${\displaystyle n\in \mathbb {N} }$,

${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k}}$

Proof by induction. Basis. In the case ${\displaystyle n=1}$, the formula is trivial.

Induction. Assume that the formula holds for a particular value of ${\displaystyle n}$. Then

{\displaystyle {\begin{aligned}(a+b)^{n+1}&=(a+b)\,(a+b)^{n}\\&=(a+b)\,\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k}\\&=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k+1}\,b^{k}+\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k}\,b^{k+1}\\&=\sum _{k=0}^{n}{\binom {n}{k}}\,a^{n-k+1}\,b^{k}+\sum _{k=1}^{n+1}{\binom {n}{k-1}}\,a^{n-k+1}\,b^{k}\\&={\binom {n}{0}}\,a^{n+1}+\sum _{k=1}^{n}\left({\binom {n}{k}}+{\binom {n}{k-1}}\right)\,a^{n-k+1}\,b^{k}+{\binom {n}{n}}\,b^{n+1}\\&={\binom {n+1}{0}}\,a^{n+1}+\sum _{k=1}^{n}{\binom {n+1}{k}}\,a^{n+1-k}\,b^{k}+{\binom {n+1}{n+1}}\,b^{n+1}\\&=\sum _{k=0}^{n+1}{\binom {n+1}{k}}\,a^{n+1-k}\,b^{k}\end{aligned}}}

Which completes the induction step.

quod erat demonstrandum

Functions

(See MATH 409 Lecture 4#Functions→)

Composition

The composition of functions ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to Z}$ is a function from ${\displaystyle X}$ to ${\displaystyle Z}$ denoted ${\displaystyle g\circ f}$, that is defined by ${\displaystyle \left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)}$ for ${\displaystyle x\in X}$.

Properties

• If ${\displaystyle f}$ and ${\displaystyle g}$ are one-to-one (injective), then composition ${\displaystyle g\circ f}$ is also one-to-one. (converse is not necessarily true; if ${\displaystyle g\circ f}$ is injective, then we only know that ${\displaystyle f}$ is injective)
• Similarly, if ${\displaystyle f}$ and ${\displaystyle g}$ are onto (surjective), then the composition ${\displaystyle g\circ f}$ is also onto. (converse is not necessarily true; if ${\displaystyle g\circ f}$ is surjective, then we only know that ${\displaystyle g}$ is surjective)
• ${\displaystyle f}$ and ${\displaystyle g}$ are bijective if and only if their composition ${\displaystyle f\circ g}$ is bijective
• If ${\displaystyle f}$ and ${\displaystyle g}$ are invertible, then their composition ${\displaystyle g\circ f}$ is also invvertible, and ${\displaystyle \left(g\circ f\right)^{-1}=f^{-1}\circ g^{-1}}$
• If ${\displaystyle id_{Z}}$ denotes the identity function on set ${\displaystyle Z}$, then ${\displaystyle f\circ id_{X}=f=id_{Y}\circ f}$ for any function.
• for any functions ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to X}$, we have ${\displaystyle g=f^{-1}}$ iff ${\displaystyle g\circ f=id_{X}}$ and ${\displaystyle f\circ g=id_{Y}}$

Images and Preimages

Given a function ${\displaystyle f:X\to Y}$, the image of a set ${\displaystyle E\subset X}$ under ${\displaystyle F}$, denoted ${\displaystyle f(E)}$ is a subset of ${\displaystyle Y}$ defined by ${\displaystyle f(e)=\left\{f(x)~\mid ~x\in E\right\}}$.

The preimage (or inverse image) of a set ${\displaystyle D\subset Y}$ under ${\displaystyle f}$, denoted ${\displaystyle f^{-1}(D)}$, is a subset of ${\displaystyle X}$ defined by ${\displaystyle f^{-1}(D)=\left\{x\in X~\mid ~f(x)\in D\right\}}$

Remark: If the function ${\displaystyle f}$ is invertible, then the pre-image ${\displaystyle f^{-1}(D)}$ is also the image of ${\displaystyle D}$ under the inverse function ${\displaystyle f^{-1}}$. However, ${\displaystyle f^{-1}(D)}$ is well-defined even if ${\displaystyle f}$ is not invertible.

Properties

• ${\displaystyle f\left(\bigcup _{\alpha \in I}E_{\alpha }\right)=\bigcup _{\alpha \in I}f(E_{\alpha })}$, ${\displaystyle f(\bigcap _{\alpha \in I}E_{\alpha })\subset \bigcap _{\alpha \in I}f(E_{\alpha })}$
• Same as previous for ${\displaystyle f^{-1}}$ and ${\displaystyle D}$
• ${\displaystyle f^{-1}(D\setminus D_{0})=f^{-1}(D)\setminus f^{-1}(D_{0})}$

Cardinality

Given two sets ${\displaystyle A}$ and ${\displaystyle B}$, ew say that ${\displaystyle A}$ is of the same cardinality as ${\displaystyle B}$ if there exists a bijective function ${\displaystyle f:A\to B}$. Notation: ${\displaystyle |A|=|B|}$.

Theorem. The relation "is of the same cardinality as" is an equivalence relation. In other words, it is:

• reflexive (${\displaystyle |A|=|A|}$)
• symmetric (${\displaystyle |A|=|B|}$ implies ${\displaystyle |B|=|A|}$), and
• transitive (${\displaystyle |A|=|B|}$ and ${\displaystyle |B|=|C|}$ implies ${\displaystyle |A|=|C|}$)

Proof. Since bijective functions show that two sets are of the same cardinality,

• Reflexivity: The identity map ${\displaystyle id_{A}:A\to A}$ is bijective.
• Symmetry: If ${\displaystyle f}$ is a bijection of ${\displaystyle A}$ onto ${\displaystyle B}$, then the inverse map ${\displaystyle f^{-1}}$ is a bijection of ${\displaystyle B}$ onto ${\displaystyle A}$.
• Transitivity: If ${\displaystyle f:A\to B}$ and ${\displaystyle g:B\to C}$ are bijections, then the composition ${\displaystyle g\circ f}$ is a bijection of ${\displaystyle A\to C}$.
quod erat demonstrandum

Countable and Uncountable Sets

A nonempty set is finite if it is of the same cardinality as ${\displaystyle \left\{1,2,\ldots ,n\right\}=[1,n]\cap \mathbb {N} }$ for some ${\displaystyle n\in \mathbb {N} }$. Otherwise, it is infinite.

An infinite set is called countable (or countably infinite) if it is of the same cardinality as ${\displaystyle \mathbb {N} }$. Otherwise it is uncountable (or uncountably infinite).

An infinite set ${\displaystyle E}$ is countable if it is possible to arrange all elements of ${\displaystyle E}$ into a single sequence (an infinite list) ${\displaystyle x_{1},x_{2},\ldots }$.

Countable Sets

Examples:

• ${\displaystyle \mathbb {N} }$ (natural numbers)
• ${\displaystyle 2\mathbb {N} }$ (even numbers)
• ${\displaystyle \mathbb {Z} }$ (integers)
• ${\displaystyle \mathbb {N} \times \mathbb {N} }$ (pairs of natural numbers)
• ${\displaystyle \mathbb {Q} }$ (rational numbers, extension of above)
• Algebraic Numbers (roots of nonzero [1]polynomials with integer coefficients)

The last bullet will be a problem on the next homework, and the hint is to count the number of polynomials first then count the roots. The third property below will also be useful

Properties

• Any infinite set contains a countable subset
• Any infinite subset of a countable set is also countable.
• The union of any finite or countable sets is also finite or countable

Uncountable Sets

Theorem. The set ${\displaystyle \mathbb {R} }$ is uncountable.

Proof. It is enough to prove that the interval ${\displaystyle (0,1)}$ is uncountable. Assume the contrary. Then all numbers from ${\displaystyle (0,1)}$ can be arranged into an infinite list ${\displaystyle x_{1},x_{2},\ldots }$. Any number ${\displaystyle x\in (0,1)}$ admits a decimal expansion of the form ${\displaystyle 0.d_{1}d_{2}d_{3}\ldots }$, where each digit ${\displaystyle d_{i}}$ is in ${\displaystyle \left\{0,1,2,3,4,5,6,7,8,9\right\}}$. In particular,

{\displaystyle {\begin{aligned}x_{1}&=0.{\color {blue}d_{11}}d_{12}d_{13}d_{14}d_{15}\ldots \\x_{2}&=0.d_{21}{\color {blue}d_{22}}d_{23}d_{24}d_{25}\ldots \\x_{3}&=0.d_{31}d_{32}{\color {blue}d_{33}}d_{34}d_{35}\ldots \\x_{4}&=0.d_{41}d_{42}d_{43}{\color {blue}d_{44}}d_{45}\ldots \\x_{5}&=0.d_{51}d_{52}d_{53}d_{54}{\color {blue}d_{55}}\ldots \end{aligned}}}

Now for any ${\displaystyle n\in \mathbb {N} }$, choose a decimal digit ${\displaystyle {\tilde {d}}_{n}}$ such that ${\displaystyle {\tilde {d}}_{n}\neq d_{nn}}$ and ${\displaystyle {\tilde {d}}_{n}}$ is neither ${\displaystyle 0}$ nor ${\displaystyle 9}$. Then ${\displaystyle 0.{\tilde {d}}_{1}{\tilde {d}}_{2}{\tilde {d}}_{3}\ldots }$ is the decimal expansion of some number ${\displaystyle {\tilde {x}}\in (0,1)}$. By construction, it is different from all expansions in the list. Although some real numbers admit two decimal expansions (e.g. ${\displaystyle 0.5000\ldots =0.4999\ldots }$), the condition ${\displaystyle {\tilde {d}}_{n}\not \in \{0,9\}}$ ensures that ${\displaystyle {\tilde {x}}}$ is not such a number. Thus ${\displaystyle {\tilde {x}}}$ is not listed. CONTRADICTION!

quod erat demonstrandum

Footnotes

1. Not identical to zero, but it can cross the ${\displaystyle x}$-axis