JKU - Mathematics for AI 1 Exercise Sheet 5

25

25

Prove by induction each of the following identities:
a) For all $n\ge 1$, the sum of the squares of the first $2n$ positive integers satisfies:

$$\sum _{k=1}^{2n}{k}^2=1^2+2^2+3^2+\cdots +(2n{)}^2=\frac{n(2n+1)(4n+1)}{3}$$

b) For all $n\ge 7$, we have

$$n!>3^n$$

a)

Induction basis ($n=1$):

$$\sum _{k=1}^2{k}^2=1^2+2^2=5⟺\frac{1\cdot (2\cdot 1+1)(4\cdot 1+1)}{3}=\frac{3}{3}\cdot 5=5$$

$✓$

Hypothesis: $\forall n\ge 1:{\sum }_{k=1}^{2n}{k}^2=\frac{n(2n+1)(4n+1)}{3}$
We need to show that: $\forall n\ge 1:{\sum }_k^{2(n+1)}{k}^2=\frac{(n+1)(2\cdot (n+1)+1)(4\cdot (n+1)+1)}{3}$

$$\begin{array}{rl}\sum _k^{2(n+1)}{k}^2& =\sum _k^{2n}{k}^2+(2n+1{)}^2+(2n+2{)}^2\\ & =\frac{n(2n+1)(4n+1)}{3}+(2n+1{)}^2+(2n+2{)}^2\text{inserting hypothesis}\\ & =\frac{n(2n+1)(4n+1)+3(2n+1{)}^2+3(2n+2{)}^2}{3}\\ & =\frac{1}{3}\left(n(8n^2+6n+1)+3(4n^2+4n+1)+3(4n^2+8n+4)\right)\\ & =\frac{1}{3}\left(8n^3+6n^2+n+12n^2+12n+3+12n^2+24n+12\right)\\ & =\frac{1}{3}\left(8n^3+30n^2+37n+15\right)\end{array}$$ $$\begin{array}{rl}\frac{(n+1)(2(n+1)+1)(4(n+1)+1)}{3}& =\frac{1}{3}(n+1)(2n+3)(4n+5)\\ & =\frac{1}{3}(n+1)(8n^2+22n+15)\\ & =\frac{1}{3}(8n^3+22n^2+15n+8n^2+22n+15)\\ & =\frac{1}{3}(8n^3+30n^2+37n+15)\text{which was to be shown}\end{array}$$

b)

Induction basis ($n=7$):

$$7!>3^7=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1>81\cdot 3^3=720\cdot 7>6581=2187$$

$✓$

Hypothesis: $\forall n\ge 7:n!>3^n$
We need to show that: $\forall n\ge 7:(n+1)!>3^{n+1}$

$$\begin{array}{rl}(n+1)!>3^{n+1}& =n!\cdot (n-1)>3^{n+1}\\ & =3^n\cdot (n-1)\underset{?}{>}{3}^{n+1}\text{inserting hypothesis}\\ & =3^n\cdot (n-1)>3^n\cdot 3\text{Holds if }(n-1)>3\end{array}$$

Since $n\ge 7$, it follows that $(n-1)\ge 6>3$. Thus, $(n+1)!>3^{n+1}$.

26

26

Let
a) $A_1=(-\infty ,2]\cap [5,\infty )$,
b) $A_2=(0,8]\cap [3,\infty )$
c) $A_3=\left\{(-1{)}^n+\frac{1}{n}\mid n\in \mathbb{N}\right\}$.

Compute, if they exist, the supremum, infimum, maximum, and minimum of $A_i$ for $i=1,2,3$.

a)

$A_1=(-\infty ,2]\cap [5,\infty )=\varnothing$
Infimum = $+\infty$, supremum = $-\infty$, no maximum, no minimum.

b)

$A_2=(0,8]\cap [3,\infty )=[3,8]$
Infimum = $3$, supremum = $8$, maximum = $8$, minimum = $3$.

c)

$A_3=\left\{(-1{)}^n+\frac{1}{n}\mid n\in \mathbb{N}\right\}=\left\{0,\frac{3}{2},-\frac{2}{3},\frac{5}{4},-\frac{4}{5},\frac{7}{6},-\frac{6}{7},\dots \right\}$
$\frac{1}{n}\to 0⟹(-1{)}^n+\frac{1}{n}\to \pm 1$
Infimum = $-1$, supremum = $\frac{3}{2}$, no maximum, no minimum.

27

27

Let $A$ and $B$ be non-empty subsets of $\mathbb{R}$, and let $A\subset B$. Prove that:
a) if sup $A$ and sup $B$ exist, then sup $A\le$ sup $B$,
b) if inf $A$ and inf $B$ exist, then inf $A\ge$ inf $B$.
c) Prove that for any real number $c$,

$$\sup (A+c)=\sup A+c\text{and}\inf (A+c)=\inf A+c,$$

where $A+c=\{a+c\mid a\in A\}$.
d) Show that for any $\lambda >0$,

$$\sup (\lambda A)=\lambda \sup A\text{and}\inf (\lambda A)=\lambda \inf A,$$

and for $\lambda <0$,

$$\sup (\lambda A)=\lambda \inf A\text{and}\inf (\lambda A)=\lambda \sup A.$$

a)

$$A\subset B⟹\forall a\in A:a\le \sup B⟹\sup B\text{ is upper bound of }A⟹\sup A\le \sup B\square$$

The subset can’t “reach higher” than the superset.

b)

$$A\subset B⟹\forall a\in A:a\ge \inf B⟹\inf B\text{ is lower bound of }A⟹\inf A\ge \inf B\square$$

Same logic flipped. The subset can’t “reach lower” either.

c) Show $\sup (A+c)=\sup A+c$. Two things to check:

(i) $\sup A+c$ is an upper bound:

$$a\le \sup A⟹a+c\le \sup A+c$$

(ii) nothing smaller works:

$$U<\sup A+c⟹U-c<\sup A⟹\exists a\in A:a>U-c⟹a+c>U$$

So $U$ fails as upper bound. $\square$

Shifting a set by $c$ shifts its sup by $c$. inf: analogous.

d) $\lambda >0$: show $\sup (\lambda A)=\lambda \sup A$.

(i) $a\le \sup A\stackrel{\lambda >0}{\Rightarrow }\lambda a\le \lambda \sup A$
(ii) $U<\lambda \sup A⟹U/\lambda <\sup A⟹\exists a\in A:a>U/\lambda \stackrel{\lambda >0}{\Rightarrow }\lambda a>U$

Positive scaling preserves order, so sup just scales along.

$\lambda <0$: show $\sup (\lambda A)=\lambda \inf A$.

(i) $a\ge \inf A\stackrel{\lambda <0}{\Rightarrow }\lambda a\le \lambda \inf A$
(ii) $U<\lambda \inf A⟹U/\lambda >\inf A⟹\exists a\in A:a<U/\lambda \stackrel{\lambda <0}{\Rightarrow }\lambda a>U$

Negative scaling flips the order: the smallest elements of $A$ become the largest of $\lambda A$, so sup and inf swap. $\square$

28

28

Find the least upper bound for the following set and prove that your answer is correct

$$S=\left\{\frac{n}{n+1}:n\in \mathbb{N}\right\}$$

$S=\left\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{4}{5},\dots \right\}$
Claim: $\sup S=1$

Proof:

$1$ is an upper bound:

$$\begin{array}{rl}\forall n\in \mathbb{N}:& \\ n& <n+1\\ \frac{n}{n+1}& <1\end{array}$$

$1$ is the least upper bound:

$$\begin{array}{r}\forall ϵ>0,\exists n\in \mathbb{N}:\\ \frac{n}{n+1}>1-ϵ\\ n>(1-ϵ)(n+1)\\ n>n-ϵn+1-ϵ\\ 0>-ϵn+1-ϵ\\ ϵn>1-ϵ\\ n>\frac{1-ϵ}{ϵ}\end{array}$$

So we can always find elements of $S$ that exceed $1-ϵ$ for any $ϵ>0$. Thus, $1$ is indeed the least upper bound.

29

29

Consider the finite field ${\mathbb{Z}}_3=\{0,1,2\}$, where all operations are performed modulo 3.
a) Write down the table of addition in ${\mathbb{Z}}_3$.
b) Write down the table of multiplication in ${\mathbb{Z}}_3$.
c) Verify that $({\mathbb{Z}}_3,+,\times )$ satisfies the field axioms; in particular, show that every nonzero element has a multiplicative inverse.

a)

$({\mathbb{Z}}_3,+)$	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

b)

$({\mathbb{Z}}_3,\times )$	0	1	2
0	0	0	0
1	0	1	2
2	0	2	1

c)

Commutativity:
The tables of addition an multiplication are symmetric.

Associativity:
$\forall x,y,z\in {\mathbb{Z}}_3:x{+}_{}(y+z)=(x+y)+z$ and $x\times (y\times z)=(x\times y)\times z$

Distributivity:
$\forall x,y,z\in {\mathbb{Z}}_3:x\times (y+z)=(x\times y)+(x\times z)$

Identity elements:
$\forall x\in {\mathbb{Z}}_3:x+0=x$ and $\forall x\in {\mathbb{Z}}_3\setminus \{0\}:x\times 1=x$

Inverses:
$0+0=0⟹-0=0$
$1+2=0⟹-1=2$
$2+1=0⟹-2=1$

$1\times 1=1⟹1^{-1}=1$
$2\times 2=1⟹2^{-1}=2$

30

30

a) Use the Binomial Theorem to expand and simplify each of the following expressions.
i. $(x+1{)}^4$
ii. $(2x-3{)}^3$
iii. $(1+x{)}^5$ and find the coefficient of $x^3$.

b) Simplify each of the following factorial expressions.
i.

$$\frac{n!}{(n-3)!}$$

ii.

$$\frac{(n+2)!-(n+1)!}{n!}$$

a)
i)

$$(x+1{)}^4=x^4+4x^3+6x^2+4x+1$$

ii)

$$\begin{array}{rl}(2x-3{)}^3& =1\cdot (2x{)}^3+3\cdot (2x{)}^2\cdot (-3)+3\cdot (2x)\cdot (-3{)}^2+1\cdot (-3{)}^3\\ & =8x^3-36x^2+54x-27\end{array}$$

b)

i)

$$\frac{n!}{(n-3)!}=\frac{1\cdot 2\cdots n}{1\cdot 2\cdots (n-3)}=n\cdot (n-1)\cdot (n-2)$$

ii)

$$\begin{array}{rl}\frac{(n+2)!-(n+1)!}{n!}& =\frac{(n+2)(n+1)\cancel{n!}-(n+1)\cancel{n!}}{\cancel{n!}}\\ & =n^2+3n+2-n-1\\ & =n^2+2n+1\\ & =(n+1{)}^2\end{array}$$

---

proof by induction, bounded, binomial coefficient, field