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\le k\le n$, we define the binomial coefficient $(\genfrac{}{}{0ex}{}{n}{k})$ ($n$ choose $k$) by

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

If $k>0$, then

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\dots (n-k+1)}{1\cdot 2\dots k}$

"$n$ choose $k$" refers to the fact that $(\genfrac{}{}{0ex}{}{n}{k})$ is the number of all $k$-element subsets of an $n$-element set.

Lemma. A helpful recursive form

$(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})$

Proof.

$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})& =\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}\\ & =\frac{n!}{(k-1)!(n-k)!}(\frac{1}{n-k+1}+\frac{1}{k})\\ & =\frac{n!}{(k-1)!(n-k)!}\cdot \frac{n+1}{k(n-k+1)}\\ & =\frac{(n+1)!}{k!(n-k+1)!}\\ & =(\genfrac{}{}{0ex}{}{n+1}{k})\end{array}$

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 $(\genfrac{}{}{0ex}{}{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{ℝ}$ and $n\in \mathbb{\mathbb{N}}$,

$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{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{array}{rl}(a+b{)}^{n+1}& =(a+b)(a+b{)}^n\\ & =(a+b)\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k\\ & =\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k+1}{b}^k+\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^{k+1}\\ & =\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k+1}{b}^k+\sum _{k=1}^{n+1}(\genfrac{}{}{0ex}{}{n}{k-1})a^{n-k+1}{b}^k\\ & =(\genfrac{}{}{0ex}{}{n}{0})a^{n+1}+\sum _{k=1}^n((\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1}))a^{n-k+1}{b}^k+(\genfrac{}{}{0ex}{}{n}{n})b^{n+1}\\ & =(\genfrac{}{}{0ex}{}{n+1}{0})a^{n+1}+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n+1}{k})a^{n+1-k}{b}^k+(\genfrac{}{}{0ex}{}{n+1}{n+1})b^{n+1}\\ & =\sum _{k=0}^{n+1}(\genfrac{}{}{0ex}{}{n+1}{k})a^{n+1-k}{b}^k\end{array}$

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 $(g\circ f)\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 ${(g\circ f)}^{-1}=f^{-1}\circ g^{-1}$
• If $i{d}_Z$ denotes the identity function on set $Z$, then $f\circ i{d}_X=f=i{d}_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=i{d}_X$ and $f\circ g=i{d}_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)=\{f(x)\mid x\in E\}$.

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)=\{x\in X\mid f(x)\in D\}$

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 $i{d}_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 $\{1,2,\dots ,n\}=[1,n]\cap \mathbb{\mathbb{N}}$ for some $n\in \mathbb{\mathbb{N}}$. Otherwise, it is infinite.

An infinite set is called countable (or countably infinite) if it is of the same cardinality as $\mathbb{\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,\dots$.

Countable Sets

Examples:

• $\mathbb{\mathbb{N}}$ (natural numbers)
• $2\mathbb{\mathbb{N}}$ (even numbers)
• $\mathbb{\mathbb{Z}}$ (integers)
• $\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}$ (pairs of natural numbers)
• $\mathbb{\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{ℝ}$ 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,\dots$. Any number $x\in (0,1)$ admits a decimal expansion of the form $0.d_1{d}_2{d}_3\dots$, where each digit $d_i$ is in $\{0,1,2,3,4,5,6,7,8,9\}$. In particular,

$\begin{array}{rl}{x}_1& =0.d_{11}{d}_{12}{d}_{13}{d}_{14}{d}_{15}\dots \\ x_2& =0.d_{21}{d}_{22}{d}_{23}{d}_{24}{d}_{25}\dots \\ x_3& =0.d_{31}{d}_{32}{d}_{33}{d}_{34}{d}_{35}\dots \\ x_4& =0.d_{41}{d}_{42}{d}_{43}{d}_{44}{d}_{45}\dots \\ x_5& =0.d_{51}{d}_{52}{d}_{53}{d}_{54}{d}_{55}\dots \end{array}$

Now for any $n\in \mathbb{\mathbb{N}}$, choose a decimal digit ${\tilde{d}}_n$ such that ${\tilde{d}}_n\ne d_{nn}$ and ${\tilde{d}}_n$ is neither $0$ nor $9$. Then $0.{\tilde{d}}_1{\tilde{d}}_2{\tilde{d}}_3\dots$ 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\dots =0.4999\dots$), the condition ${\tilde{d}}_n\in ̸\{0,9\}$ ensures that $\tilde{x}$ is not such a number. Thus $\tilde{x}$ is not listed. CONTRADICTION!

quod erat demonstrandum