MATH 409 Lecture 5

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

Lecture Slides

Review

• Principle of Well-Ordering
• Principle of Mathematical Induction
• Strong Induction

Inductive Definition

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

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

Binomial Coefficients

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

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

If $k>0$, then

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

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

Lemma. A helpful recursive form

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

Proof.

${\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 ${\binom {n}{k}}$ is the $k$^th number in the $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 $a,b\in \mathbb {R}$ and $n\in \mathbb {N}$,

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

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

Induction. Assume that the formula holds for a particular value of $n$. Then

${\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 $f:X\to Y$ and $g:Y\to Z$ is a function from $X$ to $Z$ denoted $g\circ f$, that is defined by $\left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)$ for $x\in X$.

Properties

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

Images and Preimages

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

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

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

Properties

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

Cardinality

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

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

• reflexive ($|A|=|A|$)
• symmetric ($|A|=|B|$ implies $|B|=|A|$), and
• transitive ($|A|=|B|$ and $|B|=|C|$ implies $|A|=|C|$)

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

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

quod erat demonstrandum

Countable and Uncountable Sets

A nonempty set is finite if it is of the same cardinality as $\left\{1,2,\ldots ,n\right\}=[1,n]\cap \mathbb {N}$ for some $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 $\mathbb {N}$. Otherwise it is uncountable (or uncountably infinite).

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

Countable Sets

Examples:

• $\mathbb {N}$ (natural numbers)
• $2\mathbb {N}$ (even numbers)
• $\mathbb {Z}$ (integers)
• $\mathbb {N} \times \mathbb {N}$ (pairs of natural numbers)
• $\mathbb {Q}$ (rational numbers, extension of above)
• Algebraic Numbers (roots of nonzero 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 $\mathbb {R}$ is uncountable.

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

${\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 $n\in \mathbb {N}$, choose a decimal digit ${\tilde {d}}_{n}$ such that ${\tilde {d}}_{n}\neq d_{nn}$ and ${\tilde {d}}_{n}$ is neither $0$ nor $9$. Then $0.{\tilde {d}}_{1}{\tilde {d}}_{2}{\tilde {d}}_{3}\ldots$ is the decimal expansion of some number ${\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. $0.5000\ldots =0.4999\ldots$), the condition ${\tilde {d}}_{n}\not \in \{0,9\}$ ensures that ${\tilde {x}}$ is not such a number. Thus ${\tilde {x}}$ is not listed. CONTRADICTION!

quod erat demonstrandum