how to prove it - ch6, sec6.3(Recursion) ex

This section introduces recursion and shows how it relates to mathematical induction. Also, in recursive formulae, since we can easily relate f(n+1) to f(n) so they are usually proved with mathematical induction. For similar reason, proofs involving ∑ are also easily done by induction.

=================================================================================================

Ex-1: Scratchwork:
P(1) = 1/2
P(2) = 2/3
P(3) = 3/4

It is easy enough to guess that P(n) = $\frac{n}{n+1}$

Formal Proof:

Base case: n = 1, $\frac{1}{1(1+1)}$ = $\frac{1}{2}$

Induction step:

Let, $\sum _{i=1}^n\frac{1}{i(i+1)}$.

Now, $\sum _{i=1}^{n+1}\frac{1}{i(i+1)}$
= $\sum _{i=1}^n\frac{1}{i(i+1)}$ + $\frac{1}{(n+1)(n+2)}$
= $\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}$
= $\frac{1}{n+1}(n+\frac{1}{n+2})$
= $\frac{1}{n+1}\left(\frac{(n+1{)}^2}{n+2}\right)$
= $\frac{n+1}{n+2}$


Ex-2: Base case: For n = 1,
LHS = $\frac{1}{1(1+1)(1+2)}$ = $\frac{1}{6}$
RHS = $\frac{1^2+3\left(1\right)}{4(1+1)(1+2)}$ = $\frac{4}{4.2.3}$ = $\frac{1}{6}$

clearly, LHS = RHS

Induction step:

Let, $\sum _{i=1}^n\frac{1}{i(i+1)(i+2)}=\frac{n^2+3n}{4(n+1)(n+2)}$

Now, $\sum _{i=1}^{n+1}\frac{1}{i(i+1)(i+2)}$
= $\sum _{i=1}^n\frac{1}{i(i+1)(i+2)}+\frac{1}{(n+1)(n+2)(n+3)}$
= $\frac{n^2+3n}{4(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}$
= $\frac{1}{(n+1)(n+2)}(\frac{n^2+3n}{4}+\frac{1}{n+3})$
= $\frac{(n^3+5n^2+4n)+(n^2+5n+4)}{4(n+1)(n+2)(n+3)}$
= $\frac{(n^2+5n+4)n+(n^2+5n+4)}{4(n+1)(n+2)(n+3)}$
= $\frac{(n^2+5n+4)(n+1)}{4(n+1)(n+2)(n+3)}$
= $\frac{n^2+5n+4}{4(n+2)(n+3)}$
= $\frac{(n+1{)}^2+3(n+1)}{4(n+2)(n+3)}$


Ex-3: Base case: For n = 2

LHS = $\frac{1}{(2-1)(2+1)}$ = $\frac{1}{3}$
RHS = $\frac{3.2^2-2-2}{4.2(2+1)}$ = $\frac{12-4}{4.2.3}$ = $\frac{8}{4.2.3}$ = $\frac{1}{3}$

Induction step:

Let, $\sum _{i=2}^n\frac{1}{(i-1)(i+1)}=\frac{3n^2-n-2}{4n(n+1)}$

Now, $\sum _{i=2}^{n+1}\frac{1}{(i-1)(i+1)}$
= $\sum _{i=2}^n\frac{1}{(i-1)(i+1)}+\frac{1}{n(n+2)}$
= $\frac{3n^2-n-2}{4n(n+1)}+\frac{1}{n(n+2)}$
= $\frac{1}{n}[\frac{3n^2-n-2}{4(n+1)}+\frac{1}{(n+2)}]$
= $\frac{1}{n}\left[\frac{(3n^2-n-2)(n+2)+4(n+1)}{4(n+1)(n+2)}\right]$
= $\frac{1}{n}\left[\frac{3n^3-n^2-2n+6n^2-2n-4+4n+4}{4(n+1)(n+2)}\right]$
= $\frac{1}{n}\left[\frac{3n^3+5n^2}{4(n+1)(n+2)}\right]$
= $\frac{3n^2+5n}{4(n+1)(n+2)}$
= $\frac{3(n^2+2n+1)-6n-3+5n}{4(n+1)(n+2)}$
= $\frac{3(n+1{)}^2-(n+1)-2}{4(n+1)(n+2)}$


Ex-4: Base case: For n = 0;

LHS = $\left(2\right(0)+1{)}^2$ = 1
RHS = $\frac{(0+1)(2.0+1)(2.0+3)}{3}$ = $\frac{\left(1\right)\left(1\right)\left(3\right)}{3}$ = 1

clearly, LHS = RHS

Induction step:

Let, $\sum _{i=0}^n(2i+1{)}^2=\frac{(n+1)(2n+1)(2n+3)}{3}$

Now, $\sum _{i=0}^{n+1}(2i+1{)}^2$
= $\sum _{i=0}^n(2i+1{)}^2+(2(n+1)+1{)}^2$
= $\frac{(n+1)(2n+1)(2n+3)}{3}+(2n+3{)}^2$
= $(2n+3)[\frac{(n+1)(2n+1)}{3}+(2n+3\left)\right]$
= $(2n+3)\left[\frac{(2n^2+3n+1)+(6n+9)}{3}\right]$
= $(2n+3)\left[\frac{2n^2+9n+10}{3}\right]$
= $(2n+3)\left[\frac{2n^2+4n+5n+10}{3}\right]$
= $(2n+3)\left[\frac{(n+2)(2n+5)}{3}\right]$
= $\frac{(n+2)(2n+3)(2n+5)}{3}$


Ex-5: Base case: For n = 0

LHS = $r^0$ = 1
RHS = $\frac{r^{(0+1)}-1}{r-1}$ = $\frac{r-1}{r-1}$ = 1

Induction step:

Let, $\sum _{i=0}^n{r}^i=\frac{r^{(n+1)}-1}{r-1}$

Now, $\sum _{i=0}^{n+1}{r}^i$
= $\sum _{i=0}^n{r}^i+r^{(n+1)}$
= $\frac{r^{(n+1)}-1}{r-1}+r^{(n+1)}$
= $\frac{r^{(n+1)}-1+r^{(n+2)}-r^{(n+1)}}{r-1}$
= $\frac{r^{(n+2)}-1}{r-1}$


Ex-6: Base case: For n = 1

LHS = $\frac{1}{1^2}$ = 1
RHS = $2-\frac{1}{1}$ = 1

clearly, LHS $\le$ RHS

Induction step:

Let, $\sum _{i=1}^n\frac{1}{i^2}\le 2-\frac{1}{n}$

Now, $\sum _{i=1}^{n+1}\frac{1}{i^2}$
= $\sum _{i=1}^n\frac{1}{i^2}+\frac{1}{(n+1{)}^2}$
$\le (2-\frac{1}{n})+\frac{1}{(n+1{)}^2}$
= $(2-\frac{1}{n+1})+\frac{1}{n+1}-\frac{1}{n}+\frac{1}{(n+1{)}^2}$
= $(2-\frac{1}{n+1})+\frac{(n^2+n)-(n^2+1+2n)+n}{n(n+1{)}^2}$
= $(2-\frac{1}{n+1})-\frac{1}{n(n+1{)}^2}$
$\le (2-\frac{1}{n+1})$


Ex-7:
(a) Base case: for n = 0

LHS = RHS = $a_0+b_0$

Induction step:

Let $\sum _{i=0}^n(a_i+b_i)=\sum _{i=0}^n{a}_i+\sum _{i=0}^n{b}_i$

Now, $\sum _{i=0}^{n+1}(a_i+b_i)$
= $\sum _{i=0}^n(a_i+b_i)+(a_{n+1}+b_{n+1})$
= $\sum _{i=0}^n{a}_i+\sum _{i=0}^n{b}_i+(a_{n+1}+b_{n+1})$
= $(\sum _{i=0}^n{a}_i+a_{n+1})+(\sum _{i=0}^n{b}_i+b_{n+1})$
= $\sum _{i=0}^{n+1}{a}_i+\sum _{i=0}^{n+1}{b}_i$

(b) Base case: for n = 0, LHS = RHS = $c{a}_0$

Induction step: Let $c\sum _{i=0}^n{a}_i=\sum _{i=0}^n(c.a_i)$

Now, $c\sum _{i=0}^{n+1}{a}_i$
= $c\sum _{i=0}^n{a}_i+c.a_{n+1}$
= $\sum _{i=0}^n(c.a_i)+(c.a_{n+1})$
= $\sum _{i=0}^{n+1}(c.a_i)$


Ex-8:
(a) We will let m be arbitrary natural number and prove that $\forall n\in N(n\ge m\to H_n-H_m\ge \frac{n-m}{n}$

Base case: For n = m
LHS = $H_m-H_m$ = 0 = $\frac{m-m}{m}$ = RHS

Induction step: Let n be arbitrary natural number greater than or equal to m and $H_n-H_m\ge \frac{n-m}{n}$

Now, $H_{n+1}-H_m$
= $\left(\sum _{i=1}^{n+1}\frac{1}{i}\right)-H_m$
= $(\sum _{i=1}^n\frac{1}{i}+\frac{1}{n+1})-H_m$
= $(H_n+\frac{1}{n+1})-H_m$
= $(H_n-H_m)+\frac{1}{n+1}$
$\ge \frac{n-m}{n}+\frac{1}{n+1}$
= $\frac{n^2+n-mn-m+m}{m(n+1)}$
= $\frac{n}{m}.\frac{(n+1)-m}{n+1}$ (since n $\ge$ m, so $\frac{n}{m}\ge 1$)
$\ge \frac{(n+1)-m}{n+1}$

(b) Base case: For n = 0, LHS = $H_{2^0}=H_1=1=1+\frac{0}{2}=1$ = RHS

Induction step: Let $H_{2^n}\ge 1+\frac{n}{2}$

Now, using part(a) $H_{2^{n+1}}-H_{2^n}$
$\ge \frac{2^{n+1}-2^n}{2^{n+1}}$
= $\frac{2^n(2-1)}{2^{n+1}}$
= $\frac{1}{2}$
So, $H_{2^{n+1}}-H_{2^n}\ge \frac{1}{2}$
=> $H_{2^{n+1}}\ge H_{2^n}+\frac{1}{2}$
=> $H_{2^{n+1}}\ge 1+\frac{n}{2}+\frac{1}{2}$
=> $H_{2^{n+1}}\ge 1+\frac{n+1}{2}$


Ex-9: Base case: For n = 2

LHS = $\sum _{k=1}^1{H}_k=H_1=1$
RHS = $2(1+\frac{1}{2})-2$ = 2 + 1 - 2 = 1

clearly, LHS = RHS

Induction step: Let $\sum _{k=1}^{n-1}{H}_k=n{H}_n-n$

Now, $\sum _{k=1}^n{H}_k$
= $\left(\sum _{k=1}^{n-1}{H}_k\right)+H_n$
= $n{H}_n-n+H_n$
= $(n+1)H_n-n$

Since $H_{n+1}=\sum _{i=1}^{n+1}\frac{1}{i}=\sum _{i=1}^n\frac{1}{i}+\frac{1}{n+1}$
=> $H_n=H_{n+1}-\frac{1}{n+1}$

Hence, $\sum _{k=1}^n{H}_k$
= $(n+1)H_n-n$
= $(n+1)(H_{n+1}-\frac{1}{n+1})-n$
= $(n+1)H_{n+1}-(n+1)$


Ex-10: Scratchwork:
P(1) = 1 = 2! - 1
P(2) = 5 = 3! - 1
P(3) = 23 = 4! - 1
P(4) = 119 = 5! - 1

It is easy enough to guess that P(n) = (n+1)! - 1

Theorem: $\sum _{i=1}^n\left(i\right(i!\left)\right)$ = (n+1)! - 1
Proof:

Base case: For n = 1, LHS = 1 = RHS

Induction step: Let $\sum _{i=1}^n\left(i\right(i!\left)\right)$ = (n+1)! - 1

Now, $\sum _{i=1}^{n+1}\left(i\right(i!\left)\right)$
= $\sum _{i=1}^n\left(i\right(i!\left)\right)$ + (n+1).(n+1)!
= (n+1)! - 1 + (n+1).(n+1)!
= (1 + n + 1)(n+1)! - 1
= (n + 2)(n+1)! - 1
= (n+2)! - 1


Ex-11: Scratchwork:

P(0) = 0
P(1) = 1/2
P(2) = 5/6
P(3) = 23/24

My guess: P(n) = $\frac{(n+1)!-1}{(n+1)!}$

Proof:

Base case: For n = 0, LHS = 0 = RHS

Induction step: Let $\sum _{i=0}^n\frac{i}{(i+1)!}=\frac{(n+1)!-1}{(n+1)!}$

Now, $\sum _{i=0}^{n+1}\frac{i}{(i+1)!}$
= $\sum _{i=0}^n\frac{i}{(i+1)!}+\frac{(n+1)}{(n+2)!}$
= $\frac{(n+1)!-1}{(n+1)!}+\frac{(n+1)}{(n+2)!}$
= $\frac{\left[\right(n+1)!-1](n+2)}{(n+2)!}+\frac{(n+1)}{(n+2)!}$
= $\frac{1}{(n+2)!}\left[\right(n+2)!-(n+2)+(n+1\left)\right]$
= $\frac{(n+2)!-1}{(n+2)!}$


Ex-12:
(a) Base case: n = 0, clearly $2^0$ = 1 > 0

Induction step:

Let, for an arbitrary natural number n s.t. n $\ge 1$, $2^n>n$

Now, $2^{(n+1)}$ = $2.2^n$ > $2n$ = (n + n) $\ge (n+1)$

Thus, $2^{(n+1)}\ge (n+1)$

(b) Base case: n = 9, 9! = 362880 $\ge$ 262144 = $2^{18}={\left(2^9\right)}^2$

Induction step: Let n be an arbitrary natural number s.t. n $\ge 9$ and $n!\ge {\left(2^n\right)}^2$

Now, (n+1)! = (n+1).n! $\ge (n+1).{\left(2^n\right)}^2=(n+1).2^{2n}$

since, n $\ge$ 9, so (n+1) > 4

Hence (n+1)! $\ge (n+1).2^{2n}>4.2^{2n}=2^{2(n+1)}={\left(2^{n+1}\right)}^2$

(c) Base case: n = 0, 0! = 1 $\le 2^{0^2}$

Induction step: Let n be an arbitrary natural number and n! $\le 2^{\left(n^2\right)}$

Now, (n+1)! = (n+1).n! $\le (n+1).2^{\left(n^2\right)}\le \left(2^{(1+2n)}\right).2^{\left(n^2\right)}=2^{(n+1{)}^2}$


Ex-13:
(a) Base case: n = 0, $\left(k^2\right)!\ge 1=k^{2.0}$

Induction step: Let n be an arbitrary natural number s.t. $(k^2+n)!\ge k^{2n}$

Now, $(k^2+(n+1\left)\right)!=(k^2+n+1).(k^2+n)!\ge (k^2+n+1).k^{2n}=k^{2(n+1)}+(n+1).k^{2n}\ge k^{2(n+1)}$

(b) Base case: n = $2k^2$

by putting n = $k^2$ in part(a) result, we get

$(k^2+k^2)!\ge k^{2k^2}$
=> $\left(2k^2\right)!\ge k^{2k^2}$

Induction step: Let n be an arbitrary natural number s.t $n\ge 2k^2$ and $n!\ge k^n$

Now, (n+1)! = (n+1).n! $\ge (n+1).k^n\ge k.k^n=k^{(n+1)}$


Ex-14: Let a be an arbitrary real number and m be an arbitrary natural number.

Base case: n = 0, ${\left(a^m\right)}^0=1=a^{m\left(0\right)}$

Induction step: Let n be an arbitrary natural number and $(a^m{)}^n=a^{mn}$

Now, ${\left(a^m\right)}^{(n+1)}={\left(a^m\right)}^n.a^m=a^{(mn+m)}=a^{m(n+1)}$


Ex-15: Base case: n = 0, $a_0=0=2^0-0-1$

Induction step: Let $a_n=2^n-n-1$

Now, $a_{n+1}=2a_n+n=2(2^n-n-1)+n=2^{n+1}-2n-2+n=2^{n+1}-(n+1)-1$


Ex-16: Scratchwork:
$a_n={\left(a_{n-1}\right)}^2={\left(a_{n-2}\right)}^{2^2}={\left(a_{n-3}\right)}^{2^3}...={\left(a_{n-n}\right)}^{2^n}={a_0}^{2^n}=2^{2^n}$

Thus $a_n=2^{2^n}$

Proof:

Base case: n = 0, $a_0=2=2^1=2^{2^0}$

Induction step: Let $a_n=2^{2^n}$

Now, $a_{n+1}={\left(a_n\right)}^2={\left(2^{2^n}\right)}^2=2^{2.2^n}=2^{2^{(n+1)}}$


Ex-17: Scratchwork:
$a_1=1$
$a_2=\frac{1}{2}$
$a_3=\frac{1}{3}$
$a_4=\frac{1}{4}$

..easy guess, $a_n=\frac{1}{n}$

Proof:

Base case: $a_1=\frac{1}{1}=1$

Induction step: Let $a_n=\frac{1}{n}$

Now, $a_{n+1}=\frac{a_n}{a_n+1}=\frac{1/n}{(1/n)+1}=\frac{1}{n+1}$

Note: In all the following exercises, [nCk] represents n-combination-k

Ex-18:
(a) [nC0] = $\frac{n!}{0!(n-0)!}=\frac{n!}{0!.n!}=\frac{n!}{n!.0!}=\frac{n!}{n!.(n-n)!}$ = [nCn]

(b) RHS
= [nCk] + [nC(k-1)]
= $\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{n!.(n-k+1)}{k!(n-k+1)!}+\frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1).n!}{k!(n-k+1)!}-\frac{k.n!}{k!(n-k+1)!}+\frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1).n!}{k!(n-k+1)!}-\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{(k-1)!(n-k+1)!}$
= $\frac{(n+1)!}{k!(n-k+1)!}$
= [(n+1)Ck]

(c) Base case: n = k, # of elements in $P_k\left(A\right)$ of a set A having k elements = 1 = [kCk]

Induction step: Let k be an arbitrary natural number. Let n be an arbitrary natural number s.t. $n\ge k$. For any set A, that has n elements, $P_k\left(A\right)$ has [nCk] elements.

Let A be a set containing n+1 elements and $a$ be an arbitrary element of A. Let us define a set B = A\{a}.

$P_k\left(A\right)=P_k\left(B\right)\cup \{X\cup \{x\}\mid X\in P_{k-1}(B\left)\right\}$

Since $P_k$ and $\{X\cup \{x\}\mid X\in P_{k-1}(B\left)\right\}$ are disjoint, so the # of elements in $P_k\left(A\right)$ = # of elements in $P_k\left(B\right)$ + # of elements in $\{X\cup \{x\}\mid X\in P_{k-1}(B\left)\right\}$

Then, # of elements in $P_k\left(A\right)$ = [nCk] + [nC(k-1)] = [(n+1)Ck]

(d) Let x and y be arbitrary real numbers.

Base case: n = 0, LHS = $(x+y{)}^0=1=[0C0]x^{0-0}{y}^0$

Induction step: Let $(x+y{)}^n$ = $\sum _{k=0}^n\left[nCk\right]x^{n-k}{y}^k$

Now, $(x+y{)}^{n+1}$

= $(x+y).(x+y{)}^n$
= $(x+y).\sum _{k=0}^n\left[nCk\right]x^{n-k}{y}^k$

= $(x+y)\left(\right[nC0]x^n+[nC1]x^{n-1}y+[nC2]x^{n-2}{y}^2+...+[nCn\left]y^n\right)$

= $\left(\right[nC0]x^{n+1}+[nC0\left]x^{n}y\right)+\left(\right[nC1]x^{n}y+[nC1\left]x^{n-1}{y}^2\right)+\left(\right[nC2]x^{n-1}{y}^2+[nC2\left]x^{n-2}{y}^3\right)+...+\left(\right[nCn]x{y}^n+[nCn\left]y^{n+1}\right)$

= $x^{n+1}+\left(\right[nC0]x^{n}y+[nC1\left]x^{n}y\right)+\left(\right[nC1]x^{n-1}{y}^2+[nC2\left]x^{n-1}{y}^2\right)+...+\left(\right[nC(n-1)]x{y}^n+nCn]x{y}^n)+y^{n+1}$

= $x^{n+1}+\left[\right(n+1\left)C1\right]x^{n}y+\left[\right(n+1\left)C2\right]x^{n-1}{y}^2+...+\left[\right(n+1\left)Cn\right]x{y}^n+y^{n+1}$

= $\left[\right(n+1\left)C0\right]x^{n+1}+\left[\right(n+1\left)C1\right]x^{n}y+\left[\right(n+1\left)C2\right]x^{n-1}{y}^2+...+\left[\right(n+1\left)Cn\right]x{y}^n+\left[\right(n+1\left)C\right(n+1\left)\right]y^{n+1}$

= $\sum _{k=0}^{n+1}\left[\right(n+1\left)Ck\right]x^{n-k}{y}^k$


Ex-19:
(a) In Ex-18(d) put x = y = 1 to get

$(1+1{)}^n=\sum _{k=0}^n[nCk]1^{n-k}{1}^k$
=> $2^n=\sum _{k=0}^n$

(b) Base case: For n = 1

LHS = $\sum _{k=0}^1{(-1)}^k\left[nCk\right]={(-1)}^0\left[nC0\right]+(-1{)}^1\left[nC1\right]=1-1=0$ = RHS

Induction step: Let $\sum _{k=0}^n{(-1)}^k\left[nCk\right]=0$

Now, $\sum _{k=0}^{n+1}{(-1)}^k\left[\right(n+1\left)Ck\right]$

= ${(-1)}^0\left[\right(n+1\left)C0\right]+\sum _{k=1}^n{(-1)}^k\left[\right(n+1\left)Ck\right]+{(-1)}^{n+1}\left[\right(n+1\left)C\right(n+1\left)\right]$

= ${(-1)}^0+\sum _{k=1}^n{(-1)}^k\left[\right(n+1\left)Ck\right]+{(-1)}^{n+1}$

= $1+\sum _{k=1}^n{(-1)}^k\left[\right(n+1\left)Ck\right]+{(-1)}^{n+1}$

= $1+\sum _{k=1}^n{(-1)}^k\left(\right[nCk]+[nC(k-1)\left]\right)+{(-1)}^{n+1}$

= $1+\sum _{k=1}^n{(-1)}^k\left[nCk\right]+\sum _{k=1}^n{(-1)}^k\left[nC\right(k-1\left)\right]+{(-1)}^{n+1}$

= $\left({(-1)}^0\right[nC0]+\sum _{k=1}^n{(-1)}^k[nCk\left]\right)+\sum _{k=1}^n{(-1)}^k\left[nC\right(k-1\left)\right]+{(-1)}^{n+1}$

= $\left(\sum _{k=0}^n{(-1)}^k\right[nCk\left]\right)+\sum _{k=1}^n{(-1)}^k\left[nC\right(k-1\left)\right]+{(-1)}^{n+1}$

= $\left(0\right)+\sum _{k=1}^n{(-1)}^k\left[nC\right(k-1\left)\right]+{(-1)}^{n+1}$

= $\sum _{k=1}^n{(-1)}^k\left[nC\right(k-1\left)\right]+{(-1)}^{n+1}$

Let, l = k-1, then k = l+1. Now above expression becomes

= $\sum _{l=0}^{n-1}{(-1)}^{l+1}\left[nCl\right]+{(-1)}^{n+1}$

= $\sum _{l=0}^{n-1}{(-1)}^{l+1}\left[nCl\right]+{(-1)}^{n+1}\left[nCn\right]$

= $\sum _{l=0}^n{(-1)}^{l+1}\left[nCl\right]$

= $-\sum _{l=0}^n{(-1)}^l\left[nCl\right]$

= 0


Ex-20: As given in the hint, we will prove that for all $n\ge 1$,

Base case: For n = 1
$a_1={\left(a_0\right)}^2+\frac{1}{4}=\frac{1}{4}$

clearly,

Induction step: Let n be arbitrary natural number greater than or equal to 1 and

Now, $a_{n+1}$
= ${\left(a_n\right)}^2+\frac{1}{4}$
> 0

Also, $a_{n+1}$
= ${\left(a_n\right)}^2+\frac{1}{4}$
< ${\left(\frac{1}{2}\right)}^2+\frac{1}{4}$
= $\frac{1}{4}+\frac{1}{4}$
= $\frac{1}{2}$

Thus,

my emacs cheat-sheet

This post will be a record of my random emacs cheats, will keep on updating it whenever I learn something new.

Navigation:
C-a -- Go to start of current line
M-m --Go to start of the current line after the whitespaces
C-e -- Go to end of current line
M-a -- Go to start of current sentence
M-e -- Go to end of current sentence
C-n -- goto next line
C-p -- goto prev line
C-f -- forward char
M-f -- forward word
C-b -- backward char
M-b -- backward word
M-r -- reposition point to centre/top/bottom of the page without scroll
C-v -- Scroll one page down
M-v -- Scroll one page up
C-M-v --Scroll other window
C-l -- Bring current line to the centre
C-< -- Go to start of buffer
C-> -- Go to end of buffer
M-g g -- Go to a particular line

Dired Mode Tips:
o -- open file in other buffer and move cursor there
C-o -- open file in other buffer but dont move cursor
g -- refresh dir listing
^ -- go to parent director
q -- close directory
D -- delete file/dir
+ -- create new directory
R -- rename/move file
C -- copy file

m -- mark a file
u -- unmark a file
U -- unmark all

Essential Org Mode:
tab / shift-tab : fold / unfold
M-up/down : move a headine up/down
M-RET : enter a new headline
M-left/right : increase/decrease indentation of an item but not its children
M-S-left/right : increase/decrease indentation of an item and its children
C-c C-n/p : next/previous heading
C-c C-f/b : next/previous heading, same level
C-c C-u : backward to higher level heading
S-up/down : previous/next plain list item
you can have lists. unordered list start with -/+/*  and ordered list start with number and dot e.g. 1., 2.
list line which is a  term and its description can be written as term :: description
also you can make words *bold*, /italic/, _underlined_, =code=, ~verbatim~ and +strike-through+


IDO Mode Tips:
C-f -- go to open file selection
C-b -- go back to open buffer selection
C-j -- open directory in dired mode
C-g -- cancel

Mark:

C-SPC -- Set mark at current location
C-x C-x -- Swap mark and point (or go back to most recent mark location, this can be used to go to and fro start-end of just yanked text)
C-u C-SPC -- Cycle through mark ring(stores last 16 mark locations)

Copy/Cut/Kill:
C-k -- cuts/kills current line
C-w -- cuts/kills region
M-w -- copies/save-on-kill-ring region

Yank/Paste:
C-y -- paste most recent copy/cut
M-y -- replace pasted text with earlier copied/cut text

Undo:
C-/ OR C-_ OR C-x u

Search/Replace:
C-s -- Forward search [Use M-c to toggle case-sensitivity]
C-r -- Backward search
C-s C-w -- Search the word under cursor
C-s C-s -- repeat last search query
M-% -- query replace, y for yes, n for no, ! for all
C-M-s -- regex forward search
C-M-% -- regex query replace

when in Search mode you can use..
M-c --toggle case sensitivity
M-n, M-p --go through history of past searches
(Regexp Syntax on Emacs Wiki and "M-x regexp-builder" can be useful)

Macros:
C-x ( -- Start recording a macro
C-x ) -- Finish recording a macro
C-x e -- Call the macro

Repeats:
C-u <n> -- Repeat a command n times
C-M-0 to C-M-9
M-0 to M-9
C-0 to C-9

Font:
Increase Buffer Font Size: C-x C-+
Decrease Buffer Font Size: C-x C--

Windows:
C-x +  -- balance size of all windows

Dynamic Abbreviation Expand:
M-/ -- call command dabbrev-expand

Line-Endings:
Call set-buffer-file-coding-system, then give a value of "mac", "dos", "unix". For details, see http://xahlee.org/emacs/emacs_line_ending_char.html

Deleting-Lines:
M-x flush-lines RET <regex>  RET (To delete empty lines regex would be ^\s-*$ )

Typing Ctrl-<char> :
C-q C-<char>
C-q C-j (for newline char)

Cancel:
C-g

Editing Remotely:
You can open file or dired buffer using "/ssh:user@remote_host_or_ip:/path/to/file_or_dir"
You can use emacs bookmarks for remote hosts visited frequently. Also, you can run eshell on a buffer visiting remote file/dir and that eshell will effectively be running on the remote machine.

Other Important ones:
kill-rectangle, yank-rectangle, delete-rectangle
delete-trailing-whitespace, delete-whitespace-rectangle

Emacs Daemon:
emacs --daemon[=optional_name] #starts daemon
emacsclient -c [-n] #in a X window, -n to return control to terminal
emacsclient -t #run in terminal
emacsclient -e "(kill-emacs)" #kill daemon from shell
(kill-emacs) or (save-buffers-kill-emacs) #kill daemon from within emacs frame
You might want to set following env variables..
EDITOR=emacsclient -c
VISUAL=emacsclient -c

Finding Help:
C-h k -- find out what a key does
C-h m -- info about currently active modes
C-h f -- describe a function
C-h a -- type a regex/string and find info about it
M-x describe-bindings -- list all key bindings
Use menu on top to see [mode specific] key shortcuts

Tips:
Use Incremental search for jumping around
Use repeat functionality wherever you can
Use M-/ for auto word completion

Others:
GNU Emacs Manual
GNU Emacs-Lisp Reference Manual
Org Mode Basics
Org Mode Key bindings

how to prove it - ch6, sec6.2(More Examples) ex

This section shows some example proofs to emphasize the fact that power of mathematical induction goes far beyond proving facts about various properties of natural numbers.

=================================================================================================

Ex-1:
(a) First, we prove that R' is reflexive in A'
Let x be arbitrary element of A'. Then $(x,x)\in AʹXAʹ$. Since $Aʹ\subseteq A$, so $(x,x)\in R$ also. Since $(x,x)\in AʹXAʹ$ and $(x,x)\in R$, hence $(x,x)\in Rʹ$. Since x is arbitrary, so R' is reflexive.

Second, we prove that R' is antisymmetric in A'
Let (x,y) be arbitrary element of A' x A' s.t. $(x,y)\in Rʹ$ and $(y,x)\in Rʹ$. Then $(x,y)\in R$ and $(y,x)\in R$. Since R is antisymmetric, so x = y. Thus R' is antisymmetric.

Third, we prove that R' is transitive in A'
Let (x,y) and (y,z) be arbitrary elements of A' x A' s.t. $(x,y)\in Rʹ$ and $(y,z)\in Rʹ$. Then $(x,y)\in R$ and $(y,z)\in R$. Then $(x,z)\in R$. Also $(x,z)\in AʹXAʹ$. Then $(x,z)\in Rʹ$. Since (x,y) and (y,z) are arbitrary, so R' is transitive.

Hence R' is partial order on A'

(b) First, prove that T is reflexive in A.
Let x be arbitrary element of A. If x = a, then $(x,x)\in \left\{a\right\}XA$ or else $(x,x)\in Tʹ$. Thus $(x,x)\in T$. Since x is arbitrary, so T is reflexive.

Second, we prove that T is antisymmetric on A.
Let (x,y) be arbitrary element of AxA s.t. $(x,y)\in T$ and $(y,x)\in T$. Let us consider following exhaustive set of cases.
Case#1: $(x,y)\in Tʹ$ and $(y,x)\in Tʹ$
Since T' is antisymmetric, so x = y

Case#2: $(x,y)\in \left\{a\right\}XA$ and $(y,x)\in \left\{a\right\}XA$
Then x = y = a

Case#3: $(x,y)\in Tʹ$ and $(y,x)\in \left\{a\right\}XA$
Then y = a and $y\in Aʹ$, which is not possible.

Case#4: $(x,y)\in \left\{a\right\}XA$ and $(y,x)\in Tʹ$
Then x = a and $x\in Aʹ$, which is not possible

Hence x = y. Thus T is antisymmetric.

Third, we prove that T is transitive on A.
Let (x,y) and (y,z) be arbitrary elements of A x A s.t. $(x,y)\in T$ and $(y,z)\in T$. Let us consider following exhaustive set of cases.
Case#1: $(x,y)\in Tʹ$ and $(y,z)\in Tʹ$
Then $(x,z)\in Tʹ$. Then $(x,z)\in T$

Case#2: $(x,y)\in \left\{a\right\}XA$ and $(y,z)\in \left\{a\right\}XA$
Then x = y = a. Thus $(x,z)\in \left\{a\right\}XA$. Then $(x,z)\in T$

Case#3: $(x,y)\in Tʹ$ and $(y,z)\in \left\{a\right\}XA$
Then y = a and $y\in Aʹ$. Its not possible

Case#4: $(x,y)\in \left\{a\right\}XA$ and $(y,z)\in Tʹ$
Then x = a. Since $(a,z)\in \left\{a\right\}XA$, so $(x,z)\in \left\{a\right\}XA$. Then $(x,z)\in T$

Thus $(x,z)\in T$. Hence T is transitive.

Thus T is partial order on A.

Now, let x and y be arbitrary elements of A. Let us consider following exhaustive set of cases
Case#1: x = a
Then $(x,y)\in \left\{a\right\}XA$ and hence $(x,y)\in T$

Case#2: y = a
Then $(y,x)\in \left\{a\right\}XA$ and hence $(y,x)\in T$

Case#3: $x\ne a$ and $y\ne a$
Then $x\in Aʹ$ and $y\in Aʹ$. Thus either $(x,y)\in Tʹ$ or $(y,x)\in Tʹ$. Then either $(x,y)\in T$ or $(y,x)\in T$.

Hence either $(x,y)\in T$ or $(y,x)\in T$. Since x and y are arbitrary, so T is total order on A.

Now, we prove that $R\subseteq T$
Let (x,y) be arbitrary element of A x A s.t. $(x,y)\in R$. y = a is not possible because a is R-minimal. Then $y\in Aʹ$. Let us consider following exhaustive set of cases now.

Case#1: x = a
The $(a,y)\in \left\{a\right\}XA$. Then $(a,y)\in T$. Then $(x,y)\in T$.

Case#2: $x\in Aʹ$
Then $(x,y)\in Rʹ$. Then $(x,y)\in Tʹ$. Then $(x,y)\in T$.

Hence $(x,y)\in T$. Since (x,y) is arbitrary, so $R\subseteq T$


Ex-2: Base case: T = R satisfies mentioned properties
Indcution step: Let all the subsets of A that have n elements satisfy the mentioned property.

Let B be a subset of A containing n+1 elements. Let us define a set B' = B\{b} , where b is one arbitrary element of B. Since B' has n elements, so it follows from inductive hypothesis that we can choose a relation T' on A s.t. $R\subseteq Tʹ$ and $\forall x\in Bʹ\forall y\in A\left(\right(x,y)\in Tʹ\vee (y,x)\in Tʹ)$.
Now let $A_1$ = {$x\in A\mid (x,b)\in Tʹ$} , $A_2$ = $A\backslash A_1$ and T = $Tʹ\cup \left(A_{1}X{A}_2\right)$

we will now prove that T has all the necessary properties, that is
- T is partial order on A
- $R\subseteq T$
- $\forall x\in B\forall y\in A(xTy\vee yTx)$

First, we prove that T is reflexive on A
Let x be an arbitrary element of A. Then $(x,x)\in Tʹ$. Then $(x,x)\in T$. Since x is arbitrary, so T is reflexive.

Second, we prove that T is antisymmetric on A
Let (x,y) be arbitrary element of A x A s.t. $(x,y)\in T$ and $(y,x)\in T$. Let us consider following exhaustive set of cases
Case#1: $(x,y)\in Tʹ$ and $(y,x)\in Tʹ$
Then x = y

Case#2: $(x,y)\in Tʹ$ and $(y,x)\in A_{1}X{A}_2$
Then $x\in A_2$ and $y\in A_1$. Then $(y,b)\in Tʹ$. Since $(x,y)\in Tʹ$ and $(y,b)\in Tʹ$. So $(x,b)\in Tʹ$. Then $x\in A_1$. but $x\in A_2$. This is a contradiction and hence this case is not possible.

Case#3: $(x,y)\in A_{1}X{A}_2$ and $(y,x)\in Tʹ$
not possible for same reason as above

Case#4: $(x,y)\in A_{1}X{A}_2$ and $(y,x)\in A_{1}X{A}_2$
this is also not possible as x or y can not be element of both of $A_1$ and $A_2$

Hence x = y. Since (x,y) is arbitrary, so T is antisymmetric.

Third, we prove that T is transitive on A
Let (x,y) and (y,z) be arbitrary elements of A x A s.t. $(x,y)\in T$ and $(y,z)\in T$. let us consider following exhaustive set of cases.
Case#1: $(x,y)\in Tʹ$ and $(y,z)\in Tʹ$
Then $(x,z)\in Tʹ$ and hence $(x,z)\in T$

Case#2: $(x,y)\in A_{1}X{A}_2$ and $(y,z)\in A_{1}X{A}_2$
This is not possible as y can't both be in $A_1$ and $A_2$

Case#3: $(x,y)\in Tʹ$ and $(y,z)\in A_{1}X{A}_2$
Then $y\in A_1$. Then $(y,b)\in Tʹ$. Since $(x,y)\in Tʹ$ and $(y,b)\in Tʹ$, so $(x,b)\in Tʹ$. Then $x\in A_1$. Also since $(y,z)\in A_{1}X{A}_2$, so $z\in A_2$. So $(x,z)\in A_{1}X{A}_2$. Then $(x,z)\in T$

Case#4: $(x,y)\in A_{1}X{A}_2$ and $(y,z)\in Tʹ$
TODO

Hence $(x,z)\in T$. Since (x,y) and (y,z) are arbitrary, so T is transitive.

Thus T is partial order on A.

Since $R\subseteq Tʹ$, so $R\subseteq T$.

Let x be an arbitrary element of B and y be an arbitrary element of A. Let us consider following exhaustive set of cases.

Case#1: $x\in Bʹ$
Then $(x,y)\in Tʹ$ or $(y,x)\in Tʹ$. Then $(x,y)\in T$ or $(y,x)\in T$

Case#2: x = b
If $y\in A_1$ then $(y,b)\in Tʹ$, hence $(y,b)\in T$.Or, if $y\in A_2$, then since $b\in A_1$ so $(b,y)\in A_{1}X{A}_2$ and hence $(b,y)\in T$. Thus either $(b,y)\in T$ or $(y,b)\in T$. Hence either $(x,y)\in T$ or $(y,x)\in T$.

Thus $(x,y)\in T$ or $(y,x)\in T$


Ex-3: Base case: Let a be arbitrary element of A and B = {a}. clearly a is R-smallest as it is the only one
Induction step:
Let every subset of A that has n elements contain an R-smallest element.

Let B be a set s.t. $B\subseteq A$ and has n+1 elements. Let b be an arbitrary element of B and define B' = B\{b}. Since B' has n elements, so we can choose $a\in Bʹ$ s.t. a is R-smallest in B'. Since R is total order so there are only two possible cases, Let us consider both of them
Case#1: aRb
Then a is R-smallest of B

Case#2: bRa
Then its trivial to check that b is R-smallest of B

Hence there always exists a R-smallest element for any non-empty subset of A.


Ex-4:
(a) Base case: Let a be arbitrary element of A. B = {a}. Since R is reflexive on A, so $(a,a)\in R$. Hence $(a,a)\in R\circ R$

Induction Step: Let every subset of A that has n elements has the mentioned property.

Let B be a subset of A with n+1 elements. Let b be an arbitrary element of B, and define B' = B\{b}. Since B' has n elements, so we can choose an element $x\in Bʹ$ s.t. $\forall y\in Bʹ\left(\right(x,y)\in R\circ R)$. Let us consider following possible cases.

Case#1: $(x,b)\in R\circ R$
Then $\forall y\in B\left(\right(x,y)\in R\circ R)$

Case#2: $(x,b)\notin R$
Let y be an arbitrary element of B. If y = b, then since R is reflexive, so $(b,b)\in R$ and therefore $(b,y)=(b,b)\in R\circ R$. Now suppose $y\ne b$. Then $y\in Bʹ$, so by choice of x we know that $(x,y)\in R\circ R$. Then we can choose some $z\in A$ s.t. $(x,z)\in R$ and $(z,y)\in R$. We have $(x,z)\in R$, so if $(z,b)\in R$ then $(x,b)\in R\circ R$, which contradicts with the assumption for this case. Therefore $(z,b)\in R$, so $(b,z)\in R$. Since $(b,z)\in R$ and $(z,y)\in R$, so $(b,y)\in R\circ R$. Since y is arbitrary, so $\forall y\in B\left(\right(b,y)\in R\circ R)$

(b) Let A = set of all the contestants
R = {$(x,y)\in AXA\mid xbeatsy$}

clearly, $\forall x\in A\forall y\in A(xRy\vee yRx)$

From part(a), since $A\subseteq A$, we can choose some $a\in A$ s.t. $\forall y\in A\left(\right(a,y)\in R\circ R)$. Then a is the excellent contestant. So atleast one excellent contestant exists.


Ex-5: Base case: For n = 1, $F_1$ = $2^{2^1}+1$ = 5 = 3 + 2 = $F_0+2$
Induction step: Let n be an arbitrary natural number greater than 1 s.t. $F_n$ = $F_0.F_1.F_2....F_{n-1}+2$

So, $F_0.F_1.F_2....F_{n-1}.F_n+2$
= $(F_0.F_1.F_2....F_{n-1}).F_n+2$
= $(F_n-2).F_n+2$
= $(F_n{)}^2-2F_n+2$
= $(2^{2^n}+1{)}^2-2(2^{2^n}+1)+2$
= $2^{2^{(n+1)}}+1+2\left(2^{2^n}\right)-2\left(2^{2^n}\right)-2+2$
= $2^{2^{(n+1)}}+1$
= $F_{n+1}$


Ex-6: Base case: clearly $\mid a_1\mid \le \mid a_1\mid$
Induction step: Let $\mid a_1+a_2+a_3+...+a_n\mid \le \mid a_1\mid +\mid a_2\mid +\mid a_3\mid +...+\mid a_n\mid$

Then, $\mid a_1+a_2+a_3+...+a_n+a_{n+1}\mid$
= $\mid (a_1+a_2+a_3+...+a_n)+a_{n+1}\mid$
$\le \mid a_1+a_2+a_3+...+a_n\mid +\mid a_{n+1}\mid$ (by triangle inequality)
$\le \mid a_1\mid +\mid a_2\mid +\mid a_3\mid +...+\mid a_{n+1}\mid$ (by induction hypothesis)


Ex-7:
(a) $(a-b{)}^2\ge 0$
=> $a^2+b^2-2ab\ge 0$
=> $a^2+b^2\ge 2ab$

Since a and b are positive real numbers, so ab is also positive real numbers. Now, divide both sides with ab

Then, $\frac{a}{b}+\frac{b}{a}\ge 2$

(b) $(c-a)(c-b)\ge 0$
=> $c^2-cb-ca+ab\ge 0$
=> $ab+c^2-cb\ge ca$

Since a and c are positive real numbers, so ca is also positive real numbers. Now, divide both sides with ca

=> $\frac{ab}{ca}+\frac{c^2}{ca}-\frac{cb}{ca}\ge \frac{ca}{ca}$
=> $\frac{b}{c}+\frac{c}{a}-\frac{b}{a}\ge 1$

(c) Base case: For n = 2, $\frac{a_1}{a_2}+\frac{a_2}{a_1}\ge 2$ (using result of part(a) )
Induction Step: Let $\frac{a_1}{a_2}+\frac{a_2}{a_3}+...\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}\ge n$

Now, $\frac{a_1}{a_2}+\frac{a_2}{a_3}+...\frac{a_{n-1}}{a_n}+\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}$
= $\frac{a_1}{a_2}+\frac{a_2}{a_3}+...\frac{a_{n-1}}{a_n}+(\frac{a_n}{a_1}-\frac{a_n}{a_1})+\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}$
= $(\frac{a_1}{a_2}+\frac{a_2}{a_3}+...\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1})-\frac{a_n}{a_1}+\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}$
$\ge n+(\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}-\frac{a_n}{a_1})$

If we put, c = $a_{n+1}$, b = $a_n$ and a = $a_1$, we'll see that $\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}-\frac{a_n}{a_1}\ge 1$

so, $\frac{a_1}{a_2}+\frac{a_2}{a_3}+...\frac{a_{n-1}}{a_n}+\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}\ge n+1$


Ex-8:
(a) Scratchwork: $\frac{a+b}{2}\ge \sqrt{ab}$
=> $\frac{a^2+b^2+2ab}{4}\ge ab$
=> $a^2+b^2+2ab\ge 4ab$
=> $a^2+b^2-2ab\ge 0$
=> $(a-b{)}^2\ge 0$

Formal Proof:
clearly $(a-b{)}^2\ge 0$
=> $a^2+b^2-2ab\ge 0$
=> $a^2+b^2+2ab\ge 4ab$
=> $\frac{a^2+b^2+2ab}{4}\ge ab$ (now take square root of both sides)
=> $\frac{a+b}{2}\ge \sqrt{ab}$

(b) Base case: for n=1, using part(a) result we can say that $\frac{a_1+a_2}{2}\ge a_1.a_2$

Induction step: Let $\frac{a_1+a_2+a_3+...+a_{2^n}}{2^n}\ge (a_1.a_2.a_3...a_{2^n}{)}^{\frac{1}{2^n}}$

Now, $\frac{a_1+a_2+a_3+...+a_{2^n}+a_{2^n+1}+a_{2^n+2}+...+a_{2^{n+1}}}{2^{n+1}}$
= $\frac{a_1+a_2+a_3+...+a_{2^n}}{2^{n+1}}+\frac{a_{2^n+1}+a_{2^n+2}+...+a_{2^{n+1}}}{2^{n+1}}$
= $\frac{1}{2}(\frac{a_1+a_2+a_3+...+a_{2^n}}{2^n}+\frac{a_{2^n+1}+a_{2^n+2}+...+a_{2^{n+1}}}{2^n})$

apply the inductive hypothesis now to get following...
= $\frac{1}{2}\left[\right(a_1.a_2.a_3...a_{2^n}{)}^{\frac{1}{2^n}}+(a_{2^n+1}.a_{2^n+2}...a_{2^{n+1}}{)}^{\frac{1}{2^n}}]$

Now, apply the result of part(a) to get
= $(a_1.a_2.a_3...a_{2^{n+1}}{)}^{\frac{1}{2^{n+1}}}$

(c) Base case is trivial with n = $n_0$
Induction step: Let $n\ge n_0$ s.t.



Now, Let $a_{n+1}=m=\frac{a_1+a_2+a_3+...+a_n}{n}$
=>
=>
=>
=>

So, $\frac{a_1+a_2+a_3+...+a_n+a_{n+1}}{n+1}$
= $\frac{a_1+a_2+a_3+...+a_n}{n+1}+\frac{a_{n+1}}{n+1}$
= $\frac{mn}{n+1}+\frac{m}{n+1}$
= $\frac{m(n+1)}{n+1}$
= $m$
< $(a_1.a_2.a_3...a_n.a_{n+1}{)}^{\frac{1}{n+1}}$

(d) Let it fails for some $n_0$, then using the result of part(c) we can choose some $n\ge 1$ s.t. $2^n\ge n_0$ and there is a list of length $2^n$ s.t. arithmatic-geomatric mean inequality fails. But, this contradicts result proved in part(b). Hence such a $n_0$ does not exist and arithmatic-geomatric mean inequality always holds.


Ex-9: $\frac{n}{\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3}+...+\frac{1}{a_n}}$
Let $b_k=\frac{1}{a_k}$.

Then, $\frac{n}{\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3}+...+\frac{1}{a_n}}$
= $\frac{n}{b_1+b_2+b_3+...b_n}$

now apply arithmatic-geometric mean inequality to get following
$\le \frac{1}{(b_1.b_2.b_3...b_n{)}^{\frac{1}{n}}}$
= $(b_1.b_2.b_3...b_n{)}^{\frac{-1}{n}}$
= $(a_1.a_2.a_3...a_n{)}^{\frac{1}{n}}$


Ex-10: Base case: A = $\varnothing$, $P\left(A\right)=\{\varnothing \}$, clearly it has $2^0=1$ elements

Induction Step: Let power set of every set, that have n elements, has $2^n$ elements.

Let A be a set of n+1 elements and x be an arbitrary element of A. Let, B = A\{x}. As B has n elements, so by inductive hypothesis $P\left(B\right)$ has $2^n$ elements.

Now $P\left(A\right)$ = $P\left(B\right)\cup \{y\cup \{x\}\mid y\in P(B\left)\right\}$

Number of elements in $\{y\cup \{x\}\mid y\in P(B\left)\right\}$ = $2^n$

also $P\left(B\right)$ and $\{y\cup \{x\}\mid y\in P(B\left)\right\}$ are disjoint.

So, # of elements in $P\left(A\right)$ = # of elements in $P\left(B\right)$ + # of elements in $\{y\cup \{x\}\mid y\in P(B\left)\right\}$ = $2^n+2^n$ = $2^{n+1}$


Ex-11: Base case: A set with 2 elements, A = {a,b}, $P\left(A\right)$ = {{a,b}}, clearly it has $\frac{2(2-1)}{2}$ = 1 element only

Induction Step: Let every set with n elements fulfills the given property.

Let A be a set of n+1 elements and x be an arbitrary element of A. Let, B = A\{x}.

clearly $P\left(A\right)$ = $P\left(B\right)\cup$ {{x,y} | $y\in B$ }

As B has n elements, so by inductive hypothesis $P\left(B\right)$ has $\frac{n(n-1)}{2}$ elements. Also {{x,y} | $y\in B$ } has n elements. And $P\left(B\right)$ and {{x,y} | $y\in B$ } are disjoint.

So, # of elements in $P\left(A\right)$ = # of elements in $P\left(B\right)$ + # of elements in {{x,y} | $y\in B$ }
= $\frac{n(n-1)}{2}$ + n
= $\frac{n(n+1)}{2}$


Ex-12:


Base case: For n = 1, $4^1=4$, if we divide an equilateral triangle in 4 congruent triangles. [Fig-1] shows how we can fill it with one corner removed.

Induction Step: Suppose if we divide any equilateral triangle into $4^n$ congruenet equilateral triangles, then we can fill the remain area after removing one corner with given trapezoidal tiles.

Now, if we divide a big equilateral triangle into $4^{n+1}$ congruent equilateral triangles. We can look at the resulting triangle as 4 smaller equilateral triangles each divided in $4^n$ congruent equilateral triangles as shown in [Fig-2].

Triangle ABC is divided into $4^{n+1}$ triangles. We can look at the resulting triangle as made up of triangles APQ, PBR, QRC and PQR; each of which are divided into $4^n$ congruenet equilateral triangles. If we remove one corner at A and place a tile at R as shown in [Fig-2]. Then all the 4 triangles got one corner removed and by induction hypothesis can be filled with given tiles.

Hence, when triangle ABC is divided into $4^{n+1}$ congruent triangles, it can be filled with given tiles with one corner removed.


Ex-13: Base Case: n = 1, clearly one chord divides the circle in to $\frac{1^2+1+2}{2}$ = 2 regions.

Induction step: Let the given property be true for n chords.

If we draw a new chord cutting each other n chords, then it passes through n+1 regions cutting each of them into two halves. So resulting circle has

$\frac{n^2+n+2}{2}+(n+1)$ = $\frac{n^2+3n+4}{2}$ = $\frac{(n+1{)}^2+(n+1)+2}{2}$ regions


Ex-14: The key here is that, after n chords... if you draw (n+1)th chord. The new chord will divide the circle into two halves. Take any halve and invert the colors of all the regions inside it. Then you'll end up with the desired color scheme and that proves the given statement.


Ex-15: The flaw is that $n\in A$ doesn't necessarily mean that $n+1\in A$ also


Ex-16: Induction step proves the statement with the assumption that there are atleast 3 elements inside A(as he chooses unique $a_1$, $a_2$ and $a_3$). Base case proves the statement for sets containing 1 element. None of them prove the given statement for sets containing only 2 elements. Hence the given proof is wrong.

how to prove it - ch6, sec6.1(Proof by mathematical Induction) ex

This scetion introduces another proof technique, called Mathematical Induction, to prove the statements P(n) where n is arbitrary natural number. That is n = {0, 1, 2, 3, 4, ...}. Here is how you do it.

To Prove a goal of the form $\forall n\in NP\left(n\right)$:
First prove P(0), and then prove $\forall n\in N\left(P\right(n)\to P(n+1\left)\right)$. The first of these proofs is sometimes called the *base case* and the second the *induction step*. Premise of the induction step is called the *induction hypothesis*.

Form of the final proof:
Base case: [Proof of P(0) goaes here]
Induction Step: [Proof of $\forall n\in N\left(P\right(n)\to P(n+1\left)\right)$ goes here]

Why Mathematical Induction works?
Well, certainly P(0) is true because we prove it in the base case. Also, we prove that $\forall n\in N\left(P\right(n)\to P(n+1\left)\right)$. So P(0) -> P(1). Then P(1) -> P(2). Then P(2) -> P(3). It goes on. Continuing in this way, you should be able to see that by repeatedly applying the induction step you can show that P(n) must be true for every natural number.

A small variation in the problem might be to prove the goal of the form, for all natural number n $\ge$ k, k is a natural number, P(n). Then simply the base case becomes n = k instead of n = 0.

=============================================================================================

Ex-1:
Base case: For n = 0, both sides are 0 and hence same.

Induction Step:
Let n be an arbitrary natural number s.t. 0 + 1 + 2 + ... + n = $\frac{n(n+1)}{2}$

Now, 0 + 1 + 2 + ... + n + (n+1)
= $\frac{n(n+1)}{2}$ + (n+1)
= $\frac{(n+2)(n+1)}{2}$


Ex-2: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^2+1^2+2^2+...+n^2=\frac{\left(n\right(n+1\left)\right(2n+1)}{6}$

Now, $0^2+1^2+2^2+...+n^2+(n+1{)}^2$
= $\frac{\left(n\right(n+1\left)\right(2n+1)}{6}+(n+1{)}^2$
= $\frac{(n+1)(n+2)(2n+3)}{6}$


Ex-3: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^3+1^3+2^3+...+n^3=[\frac{\left(n\right(n+1)}{2}{]}^2$

Now, $0^3+1^3+2^3+...+n^3+(n+1{)}^3$
= $[\frac{\left(n\right(n+1)}{2}{]}^2+(n+1{)}^3$
= $\frac{(n+1{)}^2(n^2+4(n+1))}{4}$
= $[\frac{(n+1)(n+2)}{2}{]}^2$


Ex-4: Scratchwork:
P(1) = 1, P(2) = 4, P(3) = 9, P(4) = 16...

its easy to guess that P(n) = $n^2$. Let us try to prove it now.

Formal Proof:

Base case: For n = 1, LHS = 1 and RHS = $1^2$ = 1. cleary LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $n\ge 1$ and 1 + 3 + 5 ... + (2n-1) = $n^2$

Now, 1 + 3 + 5 + ... + (2n-1) + (2n+1)
= $n^2+2n+1$
= $(n+1{)}^2$


Ex-5: Base case: For n = 0, both sides are 0 and hence same

Induction step:
Let n be arbitrary natural number s.t. 0.1 + 1.2 + 2.3 + ... + n(n+1) = $\frac{n(n+1)(n+2)}{3}$

Now, 0.1 + 1.2 + 2.3 + ... + n(n+1) + (n+1)(n+2)
= $\frac{n(n+1)(n+2)}{3}$ + (n+1)(n+2)
= $\frac{(n+1)(n+2)(n+3)}{3}$


Ex-6: Scratchwork: My guess using results of ex1,5 is $\frac{n(n+1)(n+2)(n+3)}{4}$
Formal Proof:

Base case: For n = 0, both sides are 0 and hence same.

Induction step:
Let n be arbitrary natural number s.t. 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) = $\frac{n(n+1)(n+2)(n+3)}{4}$

Now, 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) + (n+1)(n+2)(n+3)
= $\frac{n(n+1)(n+2)(n+3)}{4}$ + (n+1)(n+2)(n+3)
= $\frac{(n+1)(n+2)(n+3)(n+4)}{4}$


Ex-7: Guess is $\frac{3^{n+1}-1}{2}$

Base case: For n = 10, LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $3^0+3^1+3^2+...+3^n=\frac{3^{n+1}-1}{2}$

$3^0+3^1+3^2+...+3^n+3^{n+1}$
= $\frac{3^{n+1}-1}{2}+3^{n+1}$
= $\frac{3^{n+2}-1}{2}$


Ex-8: Base case: For n = 1, LHS = 1 - 1/2 = 1/2 and RHS = 1/2. clearly both sides are equal

Induction Step:
Let n be arbitrary natural number s.t. $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...+\frac{1}{2n-1}-\frac{1}{2n}=\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}$

Now, $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...+\frac{1}{2n-1}-\frac{1}{2n}+\frac{1}{2n+1}-\frac{1}{2n+2}$
= $\frac{1}{n+1}+\frac{1}{n+2}+...+\frac{1}{2n}+\frac{1}{2n+1}-\frac{1}{2n+2}$
= $\frac{1}{n+2}+...+\frac{1}{2n}+\frac{1}{2n+1}-\frac{1}{2n+2}+\frac{1}{n+1}$
= $\frac{1}{n+2}+...+\frac{1}{2n}+\frac{1}{2n+1}+\frac{1}{2n+2}$


Ex-9:
(a) Base case: For n = 0, clearly 2 divides $0^2+0=0$
Induction Step:
Let n be arbitrary natural number s.t. $2\mid n^2+n$. Then we can choose some integer k s.t. $n^2+n=2k$

$(n+1{)}^2+(n+1)$
= $n^2+2n+1+n+1$
= $(n^2+n)+2(n+1)$
= 2(k + n + 1)

clearly, $2\mid \left[\right(n+1{)}^2+(n+1)]$

(b) Base case: For n = 0, clearly 6 divides $0^3-0=0$
Induction Step:
Let n be arbitrary natural number s.t. $6\mid (n^3-n)$. Then we can choose some integer k s.t. $n^3-n=6k$

Now, $(n+1{)}^3-(n+1)$
= $n^3+1+3n^2+3n-n-1$
= $(n^3-n)+3(n^2+n)$

In Part(a) we prove that $n^2+n$ is always divisible by 2. so we can choose some integer l s.t. $n^2+n=2l$

So, $(n+1{)}^3-(n+1)$
= $(n^3-n)+3(n^2+n)$
= 6k + 3(2l)
= 6(k+l)

clearly 6 divides $(n+1{)}^3-(n+1)$


Ex-10: Base case: For n = 0, clearly 64 divides $9^0-8\left(0\right)-1=0$
Induction step:
Let n be arbitrary natural number s.t. 64 divides $9^n-8n-1$. Then we can choose some integer k s.t. $9^n-8n-1=64k$

Now, $9^{n+1}-8(n+1)-1$
= $9.9^n-8n-9$
= $9(9^n-8n-1)+64n$
= 9(64k) + 64n$$
= 64(9k + 1)

clearly 64 divides $9^{n+1}-8(n+1)-1$


Ex-11: Base case: For n = 0, clearly 9 divides $4^0+6\left(0\right)-1=0$
Induction step:
Let n be arbitrary natural number s.t. 9 divides $4^n+6n-1$. Then we can choose some integer k s.t. $4^n+6n-1=9k$

Now, $4^{n+1}+6(n+1)-1$
= $4.4^n+6n+6-1$
= $4(4^n+6n-1)-18n+9$
= $4\left(9k\right)-9(2n-1)$
= $9(4k-2n+1)$

clearly 9 divides $4^{n+1}+6(n+1)-1$


Ex-12: Base case: For n = 0, clearly (a-b) divides $(a^0-b^0)=0$
Induction step:
Let n be arbitrary natural number s.t. (a-b) divides $a^n-b^n$. Then we can choose some integer k s.t. $a^n-b^n=(a-b)k$

Now, $a^{n+1}-b^{n+1}$
= $a(a^n-b^n)+a{b}^n-b^{n+1}$
= $a(a^n-b^n)+b^n(a-b)$
= $(a-b)(ka+b^n)$


clearly (a-b) divides $a^{n+1}-b^{n+1}$


Ex-13: Base case: For n = 0, clearly (a+b) divides $a^{2\left(0\right)+1}+b^{2\left(0\right)+1}=(a+b)$
Induction step:
Let n be arbitrary natural number s.t. (a+b) divides $a^{2n+1}+b^{2n+1}$

Now, $a^{2(n+1)+1}+b^{2(n+1)+1}$
= $a^{2n+3}+b^{2n+3}$
= $a^2(a^{2n+1}+b^{2n+1})-a^2{b}^{2n+1}+b^{2n+3}$
= $a^2(a+b)k-b^{2n+1}(a^2-b^2)$
= $(a+b)(a^{2}k-b^{2n+1}(a-b\left)\right)$

clearly (a+b) divides $a^{2(n+1)+1}+b^{2(n+1)+1}$


Ex-14: Base case: For n = 10, $2^{10}=1024>10^3=1000$
Induction step:
Let n be arbitrary natural number s.t. $2^n>10^n$

Now, $2^{n+1}$
= $2.2^n$
> $2n^3$ = $n^3+n^3$ = $n^3+10n^2$ (bacause $n\ge 10$)
= $n^3+3n^2+3n^2+n^2$
> $n^3+3n^2+3n+1$ = $(n+1{)}^3$

clearly $2^{n+1}>(n+1{)}^3$


Ex-15: Base case: For n = 0, clearly $0\equiv 0\left(mod3\right)$
Inductive step:
Let n be a arbitrary natural number s.t. $n\equiv 0\left(mod3\right)$ or $n\equiv 1\left(mod3\right)$ or $n\equiv 2\left(mod3\right)$. Let us consider all the possible cases for (n+1)

Case#1: $n\equiv 0\left(mod3\right)$
Then we can choose some integer k s.t. n = 3k. Then (n + 1) = 3k + 1. Then $(n+1)-1=3k$. Thus $(n+1)\equiv 1\left(mod3\right)$

Case#2: $n\equiv 1\left(mod3\right)$
Then we can choose some integer k s.t. (n-1) = 3k. Then (n+1) = 3k+2. Then $(n+1)-2=3k$. Thus $(n+1)\equiv 2\left(mod3\right)$

Case#3: $n\equiv 2\left(mod3\right)$
Then we can choose some integer k s.t. (n-2) = 3k. Then (n+1) = 3k+3. Then $(n+1)-0=3(k+1)$. Thus $(n+1)\equiv 0\left(mod3\right)$

Thus $(n+1)\equiv 0\left(mod3\right)$ or $(n+1)\equiv 1\left(mod3\right)$ or $(n+1)\equiv 2\left(mod3\right)$


Ex-16: Base case: For n = 1. LHS = $2.2^1$ = 4, RHS = $\left(1\right)2^{1+1}=4$. clearly LHS = RHS
Induction Step:
Let n be arbitrary natural number s.t. $2.2^1+3.2^2+4.2^3+...+(n+1)2^n=n{2}^{n+1}$

Now, $2.2^1+3.2^2+4.2^3+...+(n+1)2^n+(n+2)2^{n+1}$
= $n{2}^{n+1}+(n+2)2^{n+1}$
= $n{2}^{n+1}+n{2}^{n+1}+2^{n+2}$
= $n{2}^{n+2}+2^{n+2}$
= $(n+1)2^{n+2}$


Ex-17:
(a) Base case is not proved.

(b) Scratchwork:
I could not actually guess it. So I solved it. However, after finding the answer, it seems it was so easy to guess :)

P(n) = $1.3^0+3.3^1+5.3^2+...+(2n+1)3^n$
3P(n) = $1.3^1+3.3^2+...+(2n-1)3^n+(2n+1)3^{n+1}$

P(n) - 3P(n) = $1.3^0+2.3^1+2.3^2+....+2.3^n-(2n+1)3^{n+1}$
P(n) - 3P(n) = $-1.3^0+2(3^0+3^1+3^2+...+3^n)-(2n+1)3^{n+1}$ ,now use result of ex-7
P(n) - 3P(n) = $-1+2\frac{3^{n+1}-1}{2}-(2n+1)3^{n+1}$
2P(n) = $1-2\frac{3^{n+1}-1}{2}+(2n+1)3^{n+1}$
2P(n) = $1-3^{n+1}+1+(2n+1)3^{n+1}$
2P(n) = $2+2n{3}^{n+1}$
P(n) = $1+n{3}^{n+1}$

So, $1.3^0+3.3^1+5.3^2+...+(2n+1)3^n=1+n{3}^{n+1}$

Formal Proof:

Base case: For n = 0. LHS = $1.3^0$ = 1, RHS = $1+\left(0\right)3^{0+1}$ = 1 + 0 = 1

Induction step:
Let n be arbitrary natural number s.t. $1.3^0+3.3^1+5.3^2+...+(2n+1)3^n=1+n{3}^{n+1}$

Now, $1.3^0+3.3^1+5.3^2+...+(2n+1)3^n+(2n+3)3^{n+1}$
= $1+n{3}^{n+1}+(2n+3)3^{n+1}$
= $1+n{3}^{n+1}+2n{3}^{n+1}+3.3^{n+1}$
= $1+3n{3}^{n+1}+3^{n+2}$
= $1+(n+1)3^{n+2}$


Ex-18: Note that even/odd is defined to natural numbers $\ge$ 1
Base case: for n = 1, clearly 1 is odd and

Induction step:

Let n be an arbitrary natural number. if n is even then $a^n>0$ or if n is odd then . Let us consider both the cases

Case#1: n is even and $a^n>0$
(n+1) is odd. And $a^{n+1}$ = $a.a^n$. Since a is negative and $a^n$ is positive, so

Case#2: n is odd and
(n+1) is even. And $a^{n+1}$ = $a.a^n$. Since a is negative and also $a^n$ is negative, so $a^{n+1}>0$


Ex-19:
(a) Base case: For n = 1, 0 < a < b
Induction step:
Let n be arbitrary natural number greater thant or equal to 1 s.t. .

clearly, .

Now, $b^{n+1}=b{b}^n>b{a}^n>a{a}^n=a^{n+1}$
Thus,

(b) TODO

(c) We'll prove the inequality directly.
inequality to prove is, . it can rewritten as $a^{n+1}+b^{n+1}-a{b}^n-b{a}^n>0$

Now $a^{n+1}+b^{n+1}-a{b}^n-b{a}^n$
= $a^{n+1}-a{b}^n+b^{n+1}-b{a}^n$
= $a(a^n-b^n)-b(a^n-b^n)$
= $(a-b)(a^n-b^n)$
= $(b-a)(b^n-a^n)$

from part(a),
=> $(b^n-a^n)>0$

also (b-a) > 0

Hence $a^{n+1}+b^{n+1}-a{b}^n-b{a}^n$ = $(b-a)(b^n-a^n)$ > 0

(d) Base case: For n = 2,
$(\frac{a+b}{2}{)}^2=\frac{a^2+b^2}{4}+\frac{2ab}{4}$

In part(c), putting n = 1 gives

=>

So, $(\frac{a+b}{2}{)}^2$
= $\frac{a^2+b^2}{4}+\frac{2ab}{4}$
< $\frac{a^2+b^2}{4}+\frac{a^2+b^2}{4}$ = $\frac{a^2+b^2}{2}$

Induction step:
Let n be arbitrary natural number greater than or equal to 2 s.t.

Multiplying both sides of above inequality with $\frac{a+b}{2}$, we get


=>

from part(c),
so,

Hence,

how to prove it - ch5, sec5.3(Inverses of Functions) ex

This section is collection of some theorems about inverses of a funcion. Here they are, their proofs can be looked up in the book.

1. Suppose f:A -> B. f is one-to-one and onto iff $f^{-1}$:B -> A

2. Suppose f is a function from A to B and $f^{-1}$ is a function from B to A. Then $f^{-1}\circ f=i_A$ and $f\circ f^{-1}=i_B$

3. Suppose f:A -> B.
- If there is a function g:B -> A s.t. $g\circ f=i_A$ then f is one-to-one.
- If there is a function g:B -> A s.t. $f\circ g=i_B$ then f is onto

All of the above can be combined into this one.

4. Suppose f:A -> B. Then the following statements are equivalent.
- f is one-to-one and onto
- $f^{-1}$:B -.A
- There is a function g:B->A s.t. $g\circ f=i_A$ and $f\circ g=i_B$

Now, this one is used in proofs alot.

5. Suppose f:A->B, If there exists a function g:B->A s.t. $g\circ f=i_A$ and $f\circ g=i_B$. Then f is one-to-one and onto and $g=f^{-1}$

================================================================================================

Ex-1: the person sitting immediately to the right of p

Ex-2: A\X

Ex-3: Consider, g(x) = $\frac{3x-5}{2}$.
Then $(g\circ f)\left(x\right)$
= g(f(x))
= g($\frac{2x+5}{3}$)
= $\frac{3\left(\frac{2x+5}{3}\right)-5}{2}$
= x

Thus $g\circ f=i_R$

Also, $(f\circ g)\left(x\right)$
= f(g(x))
= f($\frac{3x-5}{2}$)
= $\frac{2\left(\frac{3x-5}{2}\right)+5}{3}$
= x

Thus $f\circ g=i_R$

It follows from theorem#5 above that f is one-to-one and onto. and $f^{-1}\left(x\right)$ = g(x) = $\frac{3x-5}{2}$


Ex-4: Let g be a function from $R$ to $R$ defined as g(x) = $(\frac{x+3}{2}{)}^{\frac{1}{3}}$

Then, $(g\circ f)\left(x\right)$
= g(f(x))
= g($2x^3-3$)
= $(\frac{(2x^3-3)+3}{2}{)}^{\frac{1}{3}}$
= $(x^3{)}^{\frac{1}{3}}$
= x

Thus $g\circ f=i_R$

Also, $(f\circ g)\left(x\right)$
= f(g(x))
= f($(\frac{x+3}{2}{)}^{\frac{1}{3}}$)
= $2\left(\right(\frac{x+3}{2}{)}^{\frac{1}{3}}{)}^3-3$
= $2\left(\frac{x+3}{2}\right)-3$
= x

Thus $f\circ g=i_R$

Hence f is one-to-one and onto and $f^{-1}\left(x\right)$ = g(x) = $(\frac{x+3}{2}{)}^{\frac{1}{3}}$


Ex-5: Scratchwork:
y = $10^{2-x}$
taking log of both sides with base 10
log(y) = (2-x)log(10)
=> log(y) = 2-x
=> x = 2 - log(y)

Formal Proof:
Let $g:R^{+}\to R$ defined by g(x) = 2 - log(x)

It is easy to check that $g\circ f=i_R$ and $f\circ g=i_{R^{+}}$. Hence f is one-to-one and onto and $f^{-1}$ = g(x) = 2-log(x)


Ex-6: Scratchwork:
y = $\frac{3x}{x-2}$
=> xy - 2y = 3x
=> x(y-3) = 2y
=> x = $\frac{2y}{y-3}$

which is not defined for y = 3, clearly B = $R\backslash \left\{3\right\}$

(a),(b) B = $R\backslash \left\{3\right\}$ and consider g:B -> A defined as g(x) = $\frac{2x}{x-3}$.

Let x be an arbitrary element of A.
Then $(g\circ f)\left(x\right)$
= g(f(x))
= g($\frac{3x}{x-2}$)
= $\frac{2\left(\frac{3x}{x-2}\right)}{\left(\frac{3x}{x-2}\right)-3}$
= $\frac{6x}{3x-3(x-2)}$
= $\frac{6x}{6}$
= x

Thus $g\circ f=i_A$

Its trivial to check that $f\circ g=i_B$

Hence f is one-to-one and onto and $f^{-1}$ = g(x) = $\frac{2x}{x-3}$


Ex-7:
(a) Let x be an arbitrary real number.
Then, $(f_2\circ f_1)\left(x\right)$
= $f_2\left(f_1\right(x\left)\right)$
= $f_2(x+7)$
= $\frac{x+7}{5}$
= f(x)

Since x is arbitrary, so $f_2\circ f_1$ = f

(b) Note: g means f-inverse-1 and h means f-inverse-2.
It is trivial to compute that
g(x) = x - 7
h(x) = 5x

$(g\circ h)\left(x\right)$ = $g\left(h\right(x\left)\right)$ = $g\left(5x\right)$ = 5x-7 = $f^{-1}\left(x\right)$


Ex-8: Prove that $f\circ f^{-1}=i_B$
(a) Let b be an arbitrary element of B. Then we can choose some $a\in A$ s.t. f(a) = b. Then $f^{-1}\left(b\right)=a$
Now, $(f\circ f^{-1})\left(b\right)$ = f($f^{-1}\left(b\right)$) = f(a) = b

Since b is arbitrary, so $f\circ f^{-1}=i_B$

(b) It is given that $f^{-1}\circ f=i_A$. Let b be an arbitrary element of B.
Then $\left(\right(f^{-1}\circ f)\circ f^{-1})\left(b\right)$ = $(i_A\circ f^{-1})\left(b\right)$
=> $f^{-1}\left(\right(f\circ f^{-1}\left)\right(b\left)\right)$ = $f^{-1}\left(b\right)$

Thus, $(f\circ f^{-1})\left(b\right)=b$

Since b is arbitrary, so $f\circ f^{-1}=i_B$


Ex-9: Suppose g:A->B s.t. $f\circ g=i_B$. Let b be an arbitrary element of B. Then $(b,b)\in i_B$. Then $(b,b)\in f\circ g$. Then, we can choose $a\in A$ s.t. $(b,a)\in g$ and $(a,b)\in f$. Thus f(a) = b. Since b is arbitrary, so f is onto.


Ex-10: ($\to$) Let (b,a) be an arbitrary ordered pair in B X A s.t. $(b,a)\in g$. Since $(b,b)\in i_B$, then $(b,b)\in f\circ g$. Then we can choose some $a_0\in A$ s.t. $(b,a_0)\in g$ and $(a_0,b)\in f$. Since $(b,a)\in g$, $(b,a_0)\in g$ and g is a function, so $a=a_0$. Hence $(a,b)\in f$ and then $(b,a)\in f^{-1}$.

($\leftarrow$) Let (b,a) be an arbitrary ordered pair in B X A s.t. $(b,a)\in f^{-1}$. Then $(a,b)\in f$. Since $(a,a)\in i_A$, then $(a,a)\in g\circ f$. Then we can choose some $b_0\in B$ s.t. $(a,b_0)\in f$ and $(b_0,a)\in g$. Since $(a,b)\in f$, $(a,b_0)\in f$ and f is a function, so $b=b_0$. Hence $(b,a)\in g$.


Ex-11:
(a) Since $f\circ g=i_B$, so by theorem 5.3.3(2) f is onto. Since f is one-to-one and onto, so $f^{-1}\circ f=i_A$.
Then, g = $i_A\circ g$ = $(f^{-1}\circ f)\circ g$ = $f^{-1}\circ (f\circ g)$ = $f^{-1}\circ i_B$ = $f^{-1}$

(b) Since $g\circ f=i_A$, so by theorem 5.3.3(1) f is one-to-one. Since f is one-to-one and onto, so $f\circ f^{-1}=i_B$.
Then, g = $g\circ i_B$ = $g\circ (f\circ f^{-1})$ = $(g\circ f)\circ f^{-1}$ = $i_A\circ f^{-1}$ = $f^{-1}$

(c) Since $f\circ g=i_B$, so by theorem 5.3.3(2) f is onto. We will prove by contradiction that f is not one-to-one. Assume f is one-to-one. Since f is one-to-one and $f\circ g=i_B$, using part(a) g = $f^{-1}$. Since f is one-to-one and onto, so $f^{-1}\circ f=i_A$. Then $g\circ f=i_A$, but this contradicts with the given. Hence the assumption is false and f is not one-to-one.

Since $f\circ g=i_B$, so by theorem 5.3.3(1) g is one-to-one. We will prove by contradiction that g is not onto. Assume g is onto. Then using part(2) f = $g^{-1}$. Since g is one-to-one and onto, so $g\circ g^{-1}=i_A$. Then $g\circ f=i_A$, but this contradicts with the given. Hence the assumption is false and g is not onto.


Ex-12: Let B' = Ran(f). We'll prove that $f^{-1}$:B' -> A.
Existence:
Let b be an arbitrary element of B'. Since B' = Ran(f), so we can choose some $a\in A$ s.t. $(a,b)\in f$. Then $(b,a)\in f^{-1}$.

Uniqueness:
Let b be an arbitrary element of B' and $a_1$, $a_2$ be two arbitrary elements of A s.t. $(b,a_1)\in f^{-1}$ and $(b,a_2)\in f^{-1}$. Then $(a_1,b)\in f$ and $(a_2,b)\in f$. Since f is one-to-one, so $a_1=a_2$.

Hence $\forall b\in B\exists !a\in A\left(f^{-1}\right(b)=a)$. Thus $f^{-1}$:B' -> A


Ex-13:
(a) Its trivial to see that $\forall x\in A\forall y\in A(xRy\to f(x)=f(y\left)\right)$. So f is compatible with R. By using result of ex-18(a) in section-5.1 there exists a function h:A/R -> B s.t. for all $x\in A$, h($[x{]}_R$) = f(x)

(b) It follows straightforward from the result of ex-16, sec-5.2 that h is one-to-one.

Proof for h is onto:
Let b be an arbitrary element of B. Since f is onto, so we can choose $a\in A$ s.t. f(a) = b. clearly $a\in [a{]}_R$, so h($[a{]}_R$) = f(a) = b. Hence, h is onto.

(c) Let g(b) = {$x\in A\mid f\left(x\right)=b$}
Let a be an arbitrary element of A. Then
$(g\circ h)\left(\right[a{]}_R)$ = g(h($[a{]}_R$)) = g(f(a)) = {$x\in A\mid f\left(x\right)=f\left(a\right)$} = {$x\in A\mid (x,a)\in R$} = $[a{]}_R$. Thus, $g\circ h$ = $i_{A/R}$

Let b be an arbitrary element of B. Then
$(h\circ g)\left(b\right)$ = h(g(b)) = h({$x\in A\mid f\left(x\right)=b$})

Since f is onto, so we can choose some $a\in A$ s.t. f(a) = b. Then
{$x\in A\mid f\left(x\right)=b$} = {$x\in A\mid f\left(x\right)=f\left(a\right)$} = {$x\in A\mid xRa$} = $[a{]}_R$

Then $(h\circ g)\left(b\right)$ = h($[a{]}_R$) = f(a) = b. Thus $h\circ g$ = $i_B$

Since $g\circ h$ = $i_{A/R}$ and $h\circ g$ = $i_B$, so $h^{-1}$(b) = g(b) = {$x\in A\mid f\left(x\right)=b$}


NOTE: In all the exercises below, f|A denotes restriction of f to set A.


Ex-14:
(a) Let a be an arbitrary element of A'. Then we can choose some $b\in B$ s.t. g(b) = a.
Now $(g\circ f)\left(a\right)$ = $(g\circ f)\left(g\right(b\left)\right)$ = $(g\circ (f\circ g\left)\right)\left(b\right)$ = $(g\circ i_B)\left(b\right)$ = $g\left(i_B\right(b\left)\right)$ = g(b) = a. Since a is arbitrary, so for any $x\in Aʹ$, $(g\circ f)\left(x\right)=x$

(b) Its easy to see that $(f\mid Aʹ)\circ g=i_B$ and $g\circ (f\mid Aʹ)=i_{Aʹ}$. Hence by theorem 5.3.4, f|A' is one-to-one and onto function from A' to B. And g = $(f\mid Aʹ{)}^{-1}$


Ex-15: Let A' = Ran(g). It follows from result of ex-14(b) that g = $(f\mid Aʹ{)}^{-1}$. Also, its trivial to find that Ran(g) = B, hence A' = B. Thus g = $(f\mid B{)}^{-1}$


Ex-16:
(a) Let b be some real number s.t. f(x) = b.
Then $4x-x^2=b$
=> $x^2-4x+b=0$

This quadratic equation has real roots if $(-4{)}^2-4(1\left)\right(b)\ge 0$ $\equiv$ $16-4b\ge 0$ $\equiv$ $b\le 4$.

Hence B = {$x\in R\mid x\le 4$}

(b) Scratchwork:
Using ex-14 result, basically we want to find a function g:R -> R s.t. $f\circ g=i_R$. Then A = Ran(g) and g = $(f\mid A{)}^{-1}$.

$(f\circ g)\left(x\right)=x$
=> f(g(x)) = x

Let g(x) = y, then
f(y) = x
=> $4y-y^2=x$

one root of above quadratic equation is, y = g(x) = $2+\sqrt{4-x}$

Formal Proof:
Let g(x) = $2+\sqrt{4-x}$.

$(f\circ g)\left(x\right)$ = f(g(x)) = f($2+\sqrt{4-x}$) = $4(2+\sqrt{4-x})-(2+\sqrt{4-x}{)}^2$ = $8+4\sqrt{4-x}-(4+4-x+4\sqrt{4-x})$ = x

Hence $f\circ g=i_R$

It follows from ex-14 result that A = Ran(g) = {$x\in R\mid x\ge 2$} and $(f\mid A{)}^{-1}$(x) = g(x) = $2+\sqrt{4-x}$


Ex-17: Scratchwork:
If we prove that $g\circ f=i_P$ and $f\circ g=i_S$, then it follows from theorem 5.3.3 and 5.3.5 that f is one-to-one and onto and g = $f^{-1}$

Formal Proof:
Proof for $g\circ f=i_P$:
Let R be an arbitrary element of $P$.
Then, $(g\circ f)\left(R\right)$ = g(f(R)) = g($R\backslash i_A$) = $(R\backslash i_A)\cup i_A$ = R. Since R is arbitrary, so $g\circ f=i_P$

Proof for $f\circ g=i_S$:
Let R be an arbitrary element of $S$.
Then, $(f\circ g)\left(R\right)$ = f(g(R)) = f($R\cup i_A$) = $(R\cup i_A)\backslash i_A$

Since R is strict partial order on A, hence irreflexive and hence R and $i_A$ are disjoint. Then $(R\cup i_A)\backslash i_A$ = R. Then $(f\circ g)\left(R\right)=R$. Since R is arbitrary, so $f\circ g=i_S$

Then it follows from theorem 5.3.3 and 5.3.5 that f is one-to-one and onto and g = $f^{-1}$


Ex-18:
(a) First, we prove that R is reflexive on $F$
Let f be an arbitrary function in $F$. Let h = $i_A$. Then $h^{-1}\circ f\circ h$ = f. Hence fRf. Since f is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on $F$
Let (f,g) be arbitrary ordered pair in $FxF$ s.t. $(f,g)\in R$. Then we can choose a function $h\in P$ s.t. f = $h^{-1}\circ g\circ h$. Then $h\circ f=g\circ h$. Then $g=h\circ f\circ h^{-1}$. Let j = $h^{-1}$. Then g = $j^{-1}\circ f\circ j$. Hence $(g,h)\in R$. Since (f,g) is arbitrary, so R is symmetric.

Third, we prove that R is transitive on $F$
Let (f,g) and (g,h) be arbitrary elements of R. So we can choose functions u,v in $P$ s.t.
f = $u^{-1}\circ g\circ u$ and g = $v^{-1}\circ h\circ v$.

Then f = $u^{-1}\circ g\circ u$ = $u^{-1}\circ (v^{-1}\circ h\circ v)\circ u$ = $(v\circ u{)}^{-1}\circ h\circ (v\circ u)$. Let j = $v\circ u$. Then f = $j^{-1}\circ h\circ j$. Hence $(f,h)\in R$. Hence R is transitive.


Thus R is equivalence relation on $F$.

(b) Suppose fRg, then we can choose $h\in P$ s.t. f = $h^{-1}\circ g\circ h$.

Then $f\circ f$
= $(h^{-1}\circ g\circ h)\circ (h^{-1}\circ g\circ h)$
= $h^{-1}\circ (g\circ g)\circ h$

Hence $(f\circ f)R(g\circ g)$

(c) Suppose f has a fixed point and fRg. Then we can choose some $a\in A$ s.t. f(a) = a. We can choose $h\in P$ s.t. f = $h^{-1}\circ g\circ h$.
So f(a) = $(h^{-1}\circ g\circ h)\left(a\right)$

Let h(a) = b. Then
f(a) = $(h^{-1}\circ g)\left(b\right)$
=> a = $h^{-1}\left(g\right(b\left)\right)$

Thus $\left(g\right(b),a)\in h^{-1}$
=> $(a,g(b\left)\right)\in h$.

we assumed h(a) = b, that is $(a,b)\in h$

Since h is one-to-one, hence g(b) = b. So g has a fixed point.

how to prove it - ch5, sec5.2(One-to-one and Onto) ex

This section talks about definition of a one-to-one and/or onto function. The logic formulae for them are used to prove whether a function is one-to-one and/or onto.

One-To-One:
A function f:A -> B is called one-to-one if $\neg \exists a_1\in A\exists a_2\in A\left(f\right(a_1)=f(a_2)\wedge a_1\ne a_2)$. That is, there don't exists two different elements in A whose value of f is same.
Its easy to see that positive version of above formula(which is used more for proofs) is $\forall a_1\in A\forall a_2\in A\left(f\right(a_1)=f(a_2)\to a_1=a_2)$

Onto:
A function f:A -> B is called onto if $\forall b\in B\exists a\in A\left(f\right(a)=b)$ or that every element b in B has some element a in A s.t. $(a,b)\in f$. That means, Ran(f) = B.

One-to-One functions are also called injections and Onto functions are also called surjections. The functions that are both one-to-one and onto are called one-to-one correspondence or bijections.

===========================================================================================

Ex-1:
(a) Its not One-to-one as f(1) = f(2) = f(3). It is Onto.
(b) not a function
(c) It is one-to-one but not onto


Ex-2:
(a) Not a function
(b) g is not one-to-one as (ab,a) and (ac,a) both are in g. However, g is onto.
(c) Its both one-to-one and onto.


Ex-3:
(a) Its not one-to-one as f(a) = f(b). However, it is onto.
(b) Its not one-to-one as f(0) = f(2) = 0. It is not onto either as proven below.
We'll prove it by contradiction. Assume its onto. Let c be arbitrary real number. Then we can choose a real number x s.t.
$x^2-2x=c$
=> $x^2-2x-c=0$

For this quadratic equation, D = (4 + 4c), which is negative for any c < -1, Hence no real roots possible if c < 1, which is a contradiction and the function is not onto.
(c) Its not one-to-one as f(2.1) = f(2.2) = 2. However, it is onto.


Ex-4:
(a) It is one-to-one but not onto as there are many cities which are not capital of any nation.
(b) It is both one-to-one and onto.
(c) It is also both one-to-one and onto.


Ex-5:
(a) Prove that f is one-to-one.
Let x,y be arbitrary elements of A s.t. f(x) = f(y).
=> $\frac{x+1}{x-1}=\frac{y+1}{y-1}$
=> $\frac{(x+1)+(x-1)}{(x+1)-(x-1)}=\frac{(y+1)+(y-1)}{(y+1)-(y-1)}$
=> x = y

So, If f(x) = f(y) then x = y. Since x and y are arbitrary, so f is one-to-one.

Prove that f is onto.
Scratchwork: For any arbitrary b in A, we want to find out an a in A s.t. f(a) = b
=> $\frac{a+1}{a-1}=b$
=> $\frac{(a+1)+(a-1)}{(a+1)-(a-1)}=\frac{b+1}{b-1}$
=> $a=\frac{b+1}{b-1}$

Formal Proof: Let b be an arbitrary element of A. Let us choose x = $\frac{b+1}{b-1}$.
Then f(x)
= $\frac{\frac{b+1}{b-1}+1}{\frac{b+1}{b-1}-1}$
= $\frac{2b}{2}$
= b

Since b is arbitrary, so f is Onto.

(b) ($\to$) Let (x,y) be an arbtirary element in $f\circ f$.
So, y =$(f\circ f)\left(x\right)$
= f(f(x))
= f($\frac{x+1}{x-1}$)
= $\frac{\frac{x+1}{x-1}+1}{\frac{x+1}{x-1}-1}$
= x

So, y = x. Then $(x,y)\in i_A$.

($\leftarrow$) Let (x,x) be an arbitrary element of $i_a$. Since $(f\circ f)\left(x\right)$ = x, so $(x,x)\in f\circ f$. Since x is arbitrary, so $i_A\subseteq f\circ f$.

Hence $f\circ f=i_A$


Ex-6:
(a) f(2) = {}
(b) It is ont-to-one but not onto, for example There does not exist any real number s.t. f(x) = {1,2,3}


Ex-7:
(a) f({{1,2},{3,4}}) = {1,2} $\cup$ {3,4} = {1,2,3,4}
(b) It is not one-to-one because f({{1,2},{3}}) = f({{1},{2,3}}) = {1,2,3}. However, it is onto.


Ex-8:
(a) Suppose $g\circ f$ is onto. Let c be an arbitrary element of C, then we can choose some $a\in A$ s.t. $(g\circ f)\left(a\right)=c$. Then g(f(a)) = c. Let f(a) = b, then g(b) = c. So, for any arbitrary $c\in C$ we can choose $b\in B$ s.t. g(b) = c. Hence g is onto.

(b) Suppose $g\circ f$ is one-to-one. Let x and y be arbitrary elements of A s.t. f(x) = f(y) = u.
Now $(g\circ f)\left(x\right)$ = g(f(x)) = g(u)
Also $(g\circ f)\left(y\right)$ = g(f(y)) = g(u)

Since $g\circ f$ is one-to-one, so x = y. Since x and y are arbitrary, so f is one-to-one.


Ex-9:
(a) Suppose f is onto and g is not one-to-one.
Since g is not one-to-one, so we can choose some $b_1$ and $b_2$ in B s.t. $g\left(b_1\right)=g\left(b_2\right)$ but $b_1\ne b_2$. Since f is onto, so we can choose $a_1$ and $a_2$ in A s.t. $f\left(a_1\right)=b_1$ and $f\left(a_2\right)=b_2$ and $a_1\ne a_2$. Thus $(g\circ f)\left(a_1\right)$ = $(g\circ f)\left(a_2\right)$ and $a_1\ne a_2$. Thus $g\circ f$ is not one-to-one

(b) Suppose f is not onto and g is one-to-one. We will prove by contradiction that $g\circ f$ is not onto. Assume $g\circ f$ is onto.
Since f is not onto, so we can choose a $b\in B$ s.t. there is no $a\in A$ s.t. f(a) = b. Let g(b) = c. Since $g\circ f$ is onto, we can choose some $a\in A$ s.t. $(g\circ f)\left(a\right)=c$. Then g(f(a)) = c. But such $a$ is not possible. This is a contradiction. Hence $g\circ f$ is not onto.


Ex-10: Note: In this exercise f|C denotes the restriction of f to C.
(a) Suppose f is one-to-one. Let c and d be arbitrary elements of C s.t. (f|C)(c) = (f|C)(d) = b, where b is some element of B. Since, $C\subseteq A$, so c and d are elements of A also. Then f(c) = b and f(d) = b. Since f is one-to-one so c = d. Since c and d are arbitrary, so If f is one-to-one, then so is f|C.

(b) Suppose f|C is onto. Let b be arbitrary element of B. Since f|C is onto, so we can choose some c in C s.t. (f|C)(c) = b. Then f(c) = b. Since c is arbitrary, so If f|C is onto, then so is f.

(c) Let A = B = $R$ and C = $R^{+}$. For (a), use f(x) = |x| and for (b) use f(x) = x


Ex-11:
(a) Suppose A has more than one element. Then we can find two different arbitrary elements x and y in A s.t. $x\ne y$. Since f(x) = f(y) = b, so f is not one-to-one.

(b) Suppose B has more than one element. Then we can choose another element $c\in B$ s.t. $b\ne c$. Then there does not exist any $x\in A$ s.t. f(x) = c. Hence f is not onto.


Ex-12: ($\to$) Suppose $f\cup g$ is one-to-one. We will prove it by contradiction that Ran(f) and Ran(g) are disjoint. Assume Ran(f) and Ran(g) are not disjoint. Then we can choose some $c\in C$ s.t. there exist $a\in A$ and $b\in B$ s.t. f(a) = c and g(b) = c. Then $(f\cup g)\left(a\right)=(f\cup g)\left(b\right)=c$. But $f\cup g$ is one-to-one, so this is contradiction. Hence Ran(f) and Ran(g) are disjoint.
($\leftarrow$) Suppose Ran(f) and Ran(g) are disjoint. Let x and y be arbitrary elements of $A\cup B$ s.t. $(f\cup g)\left(x\right)=(f\cup g)\left(y\right)=c$, where $c\in C$. Then either $(x,c)\in f$ or $(x,c)\in g$ and either $(y,c)\in f$ or $(y,c)\in g$. Let us consider all the cases

Case#1: $(x,c)\in f$ and $(y,c)\in f$
Since f is one-to-one, so x = y

Case#2: $(x,c)\in g$ and $(y,c)\in g$.
Since g is one-to-one so x = y

Case#3: $(x,c)\in f$ and $(y,c)\in g$
Since Ran(f) and Ran(g) are not disjoint, so this case is not possible

Case#4: $(x,c)\in g$ and $(y,c)\in f$
Since Ran(f) and Ran(g) are not disjoint, so this case is not possible

From all these cases, it is clear that x = y. Since x and y are arbitrary, so f is one-to-one.

Hence, $f\cup g$ is one-to-one iff Ran(f) and Ran(g) are disjoint.


Ex-13: Suppose S is one-to-one.

First, we prove that for every $a\in A$, there exists atleast one $b\in B$ s.t. $(a,b)\in R$.
Let a be arbitrary element of A. Since $S\circ R$ is a function, so there exists unique $c\in C$ s.t. $(a,c)\in S\circ R$. Then we can choose some $b\in B$ s.t. $(b,c)\in S$ and $(a,b)\in R$.

Second, we prove that such a $b\in B$ is unique.
Let there exists another element $d\in B$ s.t. $(a,d)\in R$. Since Ran(R) = Dom(S) = B, so we can choose some $c_0\in C$ s.t. $(d,c_0)\in S$. Then $(a,c_0)\in S\circ R$. Since $S\circ R$ is a function and $(a,c)\in S\circ R$ and $(a,c_0)\in S$, so $c=c_0$. Then $(d,c)\in S$ and $(b,c)\in S$. Since S is one-to-one, so b = d. Hence b is unique.

Hence If S is one-to-one, then R: A -> B


Ex-14:
(a) Suppose R is reflexive and f is onto. Let b be an arbitrary element of B. Since f is onto, so we can choose some $a\in A$ s.t. f(a) = b. Since R is reflexive, so $(a,a)\in R$ and hence $(b,b)\in S$. Since b is arbitrary, so S is reflexive on B.

(b) Suppose R is transitive and f is one-to-one. Let (x,y) and (y,z) be arbitrary elements of S. So there exist unique(unique because f is function) u,v and w s.t. f(u) = x, f(v) = y, f(w) = z and $(u,v)\in R$, $(v,w)\in R$. Since R is transitive, so $(u.w)\in R$. Then $(x,z)\in S$. Since (x,y) and (y,z) are arbitrary, so S is transitive.


Ex-15:
(a) Let X be arbitrary element of A/R, so we can choose some $x\in A$ s.t. X = $[x{]}_R$. Then g(x) = X. Since X is arbitrary, so g is onto
(b) ($\to$) Suppose g is one-to-one. Since R is equivalence relation and hence reflexive, so $i_A\subseteq R$.
Let (x,y) be arbitrary element of R. Then y = $[x{]}_R$.. Then g(x) = $[x{]}_R$ = g(y). But g is one-to-one, so x = y. Hence $R\subseteq i_A$.
Thus R = $i_A$

($\leftarrow$) Suppose R = $i_A$. Let x,y be arbitrary elements of A s.t. g(x) = g(y). Then $[x{]}_R=[y{]}_R$. Then $y\in [x{]}_R$. Then $(y,x)\in R$. Then x = y and hence g is one-to-one

So g is one-to-one iff R = $i_A$


Ex-16: ($\to$) Suppose h is one-to-one. Let x,y be arbitrary elements of A s.t. f(x) = f(y). Then h($[x{]}_R$) = h($[y{]}_R$). Since h is one-to-one so $[x{]}_R=[y{]}_R$. Then xRy
($\leftarrow$) Suppose $\forall x\in A\forall y\in A\left(f\right(x)=f(y)\to x=y)$. Let $[x{]}_R$, $[y{]}_R$ are arbitrary elements of A/R s.t. h($[x{]}_R$) = h($[y{]}_R$). Then f(x) = f(y). Then xRy and then $[x{]}_R=[y{]}_R$.

Hence h is one-to-one iff $\forall x\in A\forall y\in A\left(f\right(x)=f(y)\to x=y)$


Ex-17: Suppose f is onto, g:B -> C , h:B -> C and $g\circ f$ = $h\circ f$.
(a) ($\to$) Let (b,c) be arbitrary element in g. Since f is onto so we can choose $a\in A$ s.t. f(a) = b. So $(a,c)\in g\circ f$. Then $(a,c)\in h\circ f$. Then $(b,c)\in h$. Hence $g\subseteq h$
($\leftarrow$) Using a similar argument, we can prove that $h\subseteq g$.
Hence h = g

(b) [this one is copied from solutions given in the book]
Let $c_1$ and $c_2$ be two distinct elements of C. Suppose $b\in B$. Let g and h be functions from B to C s.t. $\forall x\in B\left(g\right(x)=c_1)$, $\forall x\in B\backslash \left\{b\right\}\left(h\right(x)=c_1)$ and h(b) = $c_2$. Then $g\ne h$, so $g\circ f\ne h\circ f$ and therefore we can choose some $a\in A$ s.t. g(f(a)) $\ne$ h(f(a)). But by definition of g and h, there is only one $x\in B$ s.t. g(x) $\ne$ h(x) is x = b, so it follows that f(a) = b. Since b was arbitrary, so f is onto.


Ex-18:
(a) Suppose f is one-to-one, g:A -> B, h:A -> B and $f\circ g=f\circ h$.
($\to$) Let (a,b) be arbitrary element of g. So we can choose $c\in C$ s.t. $(b,c)\in f$. Then $(a,c)f\circ g$. Then $(a,c)f\circ h$. Then we can choose a $b_0\in B$ s.t. $(a,b_0)\in f$. Since f is one-to-one, so $b=b_0$. Hence $(a,b)\in h$. Thus $g\subseteq h$.
($\leftarrow$) Using a similar argument, $h\subseteq g$.

Thus g = h.

(b) Let $b_1$ and $b_2$ be arbitrary elements of B s.t. f($b_1$) = f($b_2$). Let us define g,h s.t. $\forall x\in A\left(g\right(x)=b_1)$ and $\forall x\in A\left(h\right(x)=b_2)$.
Now for every $x\in A$, $(f\circ g)\left(x\right)$ = f(g(x)) = f($b_1$) = f($b_2$) = f(h(x)) = $(f\circ h)\left(x\right)$. Thus $f\circ g$ = $f\circ h$. Then g = h. Then for any $x\in A$, g(x) = h(x) and hence $b_1$ = $b_2$. Since $b_1$ and $b_2$ are arbitrary, so f is one-to-one.


Ex-19:
(a) Proof for hRf:
Consider j: R -> R defined as j(x) = $(x-1{)}^2+1$

Let x be an arbitrary real number, then $(j\circ f)\left(x\right)$ = j(f(x)) = $j(x^2+1)$ = $x^4+1$ = h(x). Since x is arbitrary, so h = $j\circ f$. Hence hRf.

Proof for gRf is not true:
We will prove it by contradiction. Assume we can choose a function $j\in F$ s.t. g = $j\circ f$. Let x be an arbitrary real number. Then, g(x) = $(j\circ f)\left(x\right)$
=> $x^3+1$ = $j(x^2+1)$
=> j(x) = ${\sqrt{x-1}}^3+1$

But then j is undefined for anything less than 1 and then $j\notin F$, which is a contradiction. Hence such a function can't exist and hence gRf is not true.

(b) First, we prove that R is reflexive.
Let f be an arbitrary function in $F$. Let x be an arbitrary real number. Then $(i_R\circ f)\left(x\right)$ = $i_R\left(f\right(x\left)\right)$ = f(x). Since x is arbitrary, so f = $i_R\circ f$. Thus fRf. Since f is arbitrary, so R is reflexive on $F$.

Second, we prove that R is transitive.
Let (f,g) and (g,h) be arbitrary elements of R. Then we can choose two functions $j_1$ and $j_2$ s.t. f = $j_1\circ g$ and g = $j_2\circ h$. Let x be arbitrary real number. Then $(j_1\circ g)\left(x\right)$ = $j_1\left(g\right(x\left)\right)$ = $j_1\left(j_2\right(h\left(x\right)\left)\right)$ = $(j_1\circ j_2)\left(h\right(x\left)\right)$. Let j = $j_1\circ j_2$. Then $(j_1\circ g)\left(x\right)$ = $(j\circ h)\left(x\right)$. Since x is arbitrary, so f = $j\circ h$. Thus fRh. So R is transitive.

Hence R is preorder.

(c) Let f be an arbitrary function in $F$. Let x be an arbitrary real number. $(f\circ i_R)\left(x\right)$ = f($i_R\left(x\right)$) = f(x). Since x is arbitrary, so f = $f\circ i_R$. So $(f,i_R)\in R$.

(d) Suppose f is arbitrary function in $F$.
($\to$) Suppose $i_{R}Rf$. Then we can choose $j\in F$ s.t. $i_R=j\circ f$. Let x and y be arbitrary real numbers s.t. f(x) = f(y).
Then x = $i_R\left(x\right)$ = $(j\circ f)\left(x\right)$ = j(f(x)) = j(f(y)) = $(j\circ f)\left(y\right)$ = $i_R\left(y\right)$ = y. Thus x = y and hence f is one-to-one.

($\leftarrow$) Suppose f is one-to-one. Let A = Ran(f) and h = $f^{-1}\cup \left(\right(R\backslash A\left)X\right\{0\left\}\right)$.
Proof for h:R -> R :
Existence And Uniqueness: Let x be an arbitrary real number. Let us consider following exhaustive set of cases.

Case#1: $x\in A$
Then we can choose a unique(unique because f is one-to-one) real number y s.t. f(y) = x. Then $(y,x)\in f$. Then $(x,y)\in f^{-1}$. Then $(x,y)\in h$. So h(x) = y.

Case#2: $x\notin A$
Then $x\in R\backslash A$. Then $(x,0)\in \left(\right(R\backslash A\left)X\right\{0\left\}\right)$. Then $(x,0)\in h$. So h(x) = 0

hence h is a function from R to R.

Proof for $i_R=h\circ f$:
Let x be an arbitrary real number. Then $(h\circ f)\left(x\right)$ = h(f(x)) = x = $i_R\left(x\right)$. Since x is arbitrary, so $i_R=h\circ f$

Hence $i_{R}Rf$

(e) Let f be an arbitrary element in $F$. Using result of Ex.14(a) of section 5.1, g = $g\circ f$. Hence gRf.

(f) Suppose g is a constant function, then we can choose a real number c s.t. for every real number x, g(x) = c.

($\to$) Suppose $\forall f\in F\left(fRg\right)$. Then we can choose some function j s.t. f = $j\circ g$. Let x be an arbitrary real number. Then f(x) = $(j\circ g)\left(x\right)$ = j(g(x)) = j(c) = constant. Hence f is a constant function.

($\leftarrow$) Suppose f is a constant function. Then there is some real number d s.t. for every real number x, f(x) = d. Let us define a function j s.t. j(c) = d. Let x be an arbitrary real number. Then $(j\circ g)\left(x\right)$ = j(g(x)) = j(c) = d = f(x). Since x is arbitrary so f = $j\circ g$. Hence fRg.

(g) Proof for ": set of all one-to-one functions from $R$ to $R$ is the largest element of $F/S$ ":
Let $[g{]}_S$ be the set of all one-to-one functions in $F$. Using result of part(d), we know that $i_{R}Rg$. Hence we can choose a $j_1\in F$ s.t. $i_R=j_1\circ g$.
Let f be an arbitrary function in $F$. Then using result of part(c) $fR{i}_R$. Then we can choose a function $j_2\in F$ s.t. $f=j_2\circ i_R$. Let us define a function h = $j_2\circ j_1$. Let x be an arbitrary real number.
Then $(h\circ g)\left(x\right)$
= h(g(x))
= $(j_2\circ j_1)\left(g\right(x\left)\right)$
= $j_2\left(j_1\right(g\left(x\right)\left)\right)$
= $j_2\left(\right(j_1\circ g\left)\right(x\left)\right)$
= $j_2\left(i_R\right(x\left)\right)$
= $(j_2\circ i_R)\left(x\right)$
= f(x)

Thus f = $h\circ g$. Hence fRg. And, so $\left[f{]}_{S}T\right[g{]}_S$. Since f is arbitrary so $\forall f\in F\left(\right[f{]}_{S}T\left[g{]}_S\right)$, where $[g{]}_S$ is set of all one-to-one functions in $F$. Hence Set of all one-to-one functions in $F$ is the largest element of $F/S$ in T.

Proof for ": set of all constant functions from $R$ to $R$ is the smallest element of $F/S$ ":
Let g be a constant function and f be an arbitrary function in $F$. Using the result of part(e) gRf. Then $\left[g{]}_{S}T\right[f{]}_S$. Hence set of all constant functions is smallest element of $F/S$

how to prove it - ch5, sec5.1(Functions) ex

Function:
Suppose F is a relation from A to B. Then F is called a function from A to B if for every $a\in A$ there is *exactly one* $b\in B$ s.t. $(a,b)\in F$. In other words, F is a function if
  $\forall a\in A\exists !b\in B\left(\right(a,b)\in F)$
This unique $b\in B$ is called "the valuf of F at a", "the image of a under F", "the result of applying F on a" or just "F of a" or F(a).

If F is a function from A to B, its denoted by, F:A -> B

Often a function f from A to B is specified by giving a rule that can be used to determine f(a). However, one should always remember that such a rule is not mandatory and any subset of A X B that satisfies the requirements of function definition, is a function from A to B.

Note that, a relation is a function can be proved by proving the existence and uniqueness of a $b\in B$ for every $a\in A$.

Some Important Theorems:

1. Suppose f and g are functions from A to B. If $\forall a\in A\left(f\right(a)=g(a\left)\right)$ then f = g
2. Suppose f:A -> B and g:B -> C. Then $g\circ f$:A -> C and ($g\circ f$)(a) = g(f(a)). Note that $g\circ f$ is also the composition of g and f, so all the properties of composition are still valid.

=============================================================================================

Ex-1:
(a) Yes
(b) No, because f(1) is not unique
(c) Yes


Ex-2:
(a) No, f(d) is undefined
(b) No, for example f(ab) = a = b
(c) Yes


Ex-3:
(a) f(a) = b, f(b) = b, f(c) = a
(b) f(2) = 2*2 - 2(2) = 0
(c) f(pi) = f(3.14) = 3, f(-pi) = f(-3.14) = -4


Ex-4:
(a) Rome
(b) {1,2,3}\{1,3} = {2}
(c) f(2) = (3,1)


Ex-5: $L\circ H$ is identity relation on $N$. $H\circ L$ of a city c is the name of the city that is capital of the nation that has c.


Ex-6:
$f\circ g$(x)
= f(g(x))
= f(2x - 1)
= $\frac{1}{(2x-1{)}^2+2}$
= $\frac{1}{4x^2+1-4x+2}$
= $\frac{1}{4x^2-4x+3}$

$g\circ f$(x)
= g(f(x))
= g($\frac{1}{x^2+2}$)
= $2\frac{1}{x^2+2}-1$
= $\frac{2-x^2-2}{x^2+2}$
= $\frac{-x^2}{x^2+2}$


Ex-7: Note: in this exercixe I'm denoting restriction of f to C as f|C
(a) Existence:
Let c be an arbitrary element of C. Since $C\subseteq A$, so $c\in A$. Since f:A -> B, so we can choose some $b\in B$ s.t. $(c,b)\in f$. Also, $(c,b)\in$ C x B. Then $(c,b)\in f\cap CxB$. Thus b = (f|C)(c).
Uniqueness:
Let c be an arbitrary clement of C. Assume b,d are arbitrary elements of B s.t. $(c,b)\in f\mid C$ and $(c,d)\in f\mid C$. Then $(c,b)\in f$ and $(c,d)\in f$. Since f is a function, so b = d.

Hence f|C is a function.

Now, prove that f(c) = f|C.
clearly $(c,f(c\left)\right)\in f$. Since f:A->B, so $f\left(c\right)\in B$ and hence $(c,f(C\left)\right)\in CxB$. Then $(c,f(c\left)\right)\in f\cap CxB$. Thus $(c,f(c\left)\right)\in f\mid C$. So f(c) = (f|C)(c)

(b) ($\to$) Suppose g = (f|C). Let (c,b) be an arbitrary element of g. It follows from the assumption that $(c,b)\in (f\mid C)$. Then $(c,b)\in f$. Since (c,b) is arbitrary, so $g\subseteq f$.
($\leftarrow$) Suppose $g\subseteq f$.
Let (c,b) be an arbitrary element of g. Since $g\subseteq f$, so $(c,b)\in f$ and also $(c,b)\in CxB$. Then $(c,b)\in f\cap CxB$. Then $(c,b)\in f\mid C$. Since (c,b) is arbitrary, so $g\subseteq f\mid C$.
Let (c,b) be an arbitrary element of f|C. Then $(c,b)\in f$ and $(c,b)\in CxB$. Since $c\in C$ and g:C -> B, so we can choose a particular $d\in B$ s.t. $(c,d)\in g$. Since $g\subseteq f$, so $(c,d)\in f$. Since $(c,b)\in f$ and and $(c,d)\in f$ and f is a function, so b = d. Since $(c,d)\in g$, so $(c,b)\in g$. Since (c,b) is arbitrary, so $(f\mid C)\subseteq g$.
Hence g = f|C

(c) g:$Z\to R$, g(x) = 2x + 3
h:$R\to R$, h(x) = 2x + 3

Prove that g = h|$Z$ = $h\cap ZxR$

($\to$) Let (z,2z + 3) be arbitrary element of g. Since $z\in Z$, so $z\in R$ also. Then $(z,2z+3)\in h$. Also $(z,2z+3)\in ZxR$. Thus $(z,2z+3)\in h\mid Z$. Hence $g\subseteq h\mid Z$
($\leftarrow$) Let (r,s) be arbitrary element of h|$Z$. Then $(r,s)\in h$ and $(r,s)\in ZxR$. Then $r\in Z$ and so $(r,2r+3)\in g$. Since $(r,s)\in h$, so s = 2r + 3. Then $(r,s)\in g$. Since (r,s) is arbitrary so $h\mid Z\subseteq g$.

Hence g = $h\mid Z$


Ex-8: We will prove by contradiction that $i_A$ is the only relation on A that is equivalence relation on A and a function from A to A as well.
Proof: Suppose $i_A$ is not the only such relation. Assume there is another relation h which is equivalence relation on A and a function as well. Let (x,y) be an arbitrary element in h. Since h reflexive, so $(x,x)\in h$ as well. Since h is a function, so x = y. Then h is $i_A$.


Ex-9:In this exercise f|C denotes restriction of f to C.
(a) Existence:
Let x be an arbitrary element of $A\cup B$. Let us consider the two possible cases.
Case#1: $x\in A$
Then we can choose a particular $c\in C$ s.t. $(x,c)\in f$. Then $(x,c)\in g\cup f$

Case#2: $x\in B$
Then we can choose a particular $c\in C$ s.t. $(x,c)\in g$. Then $(x,c)\in g\cup f$

From above cases its proven that we can always find a $c\in C$ s.t. $(x,c)\in g\cup f$

Uniqueness:
Let x be an arbitrary element of $A\cup B$. Assume c,d be arbitrary elements of C s.t. $(x,c)\in g\cup f$ and $(x,d)\in g\cup f$. Let us consider all the possible cases
Case#1: $(x,c)\in g$ and $(x,d)\in g$
Then c = d

Case#2: $(x,c)\in f$ and $(x,d)\in f$
Then c = d

Case#3: $(x,c)\in f$ and $(x,d)\in g$
Since $(x,c)\in f$, so $x\in A$. Since $(x,d)\in g$, so $x\in B$. But A and B are disjoint, so x can't belong to both and hence this case is not possible

Case#4: $(x,c)\in g$ and $(x,d)\in f$
This case is also not possible for the same reason as above

Hence c = d

Thus $g\cup f$ is a function from $A\cup B$ to C.
(b) ($\to$) Suppose $f\cup g$:$A\cup B$ -> C.
Let (a,c) be an arbitrary element of f|($A\cap B$). Then $(a,c)\in f$ and $(a,c)\in A\cap BxC$. Then $a\in B$, so we can choose a particular $d\in C$ s.t. $(a,d)\in g$. Then $(a,d)\in f\cup g$. Since $(a,c)\in f$, so $(a,c)\in f\cup g$. Then c = d. Hence $(a,c)\in g$. Thus $(a,c)\in g\cap A\cap B$. Since (a,c) is arbitrary, so $f\mid A\cap B\subseteq g\mid A\cap B$
By a similar argument, we can prove that $g\mid A\cap B\subseteq f\mid A\cap B$
Hence $f\mid A\cap B$ = $g\mid A\cap B$

($\leftarrow$) Suppose $f\mid A\cap B$ = $g\mid A\cap B$.
Existence:
Let x be an arbitrary element of $A\cup B$. Then either $x\in A$ or $x\in B$. In both the cases there exists some $c\in C$ s.t. $(x,c)\in f\cup g$.

Uniqueness:
Let x be an arbitrary element of $A\cup B$. Let c,d be arbitrary elements of C s.t. $(x,c)\in f\cup g$ and $(x,d)\in f\cup g$. Now let us consider all possible cases
Case#1: $(x,c)\in f$ and $(x,d)\in f$
Then c = d

Case#2: $(x,c)\in g$ and $(x,d)\in g$
Then c = d

Case#3: $(x,c)\in f$ and $(x,d)\in g$
Then $x\in A\cap B$. Since $(x,c)\in (A\cap B)xC$, so $(x,c)\in f\mid A\cap B$. By similar argument, $(x,d)\in g\mid A\cap B$. Since $f\mid A\cap B=g\mid A\cap B$, so $(x,d)\in f\mid A\cap B$ as well. Hence c = d

Case#4: $(x,c)\in g$ and $(x,d)\in f$
By using similar argument as above, c = d

Hence $f\cup g$:$A\cup B$ -> C


Ex-10:
(a) Existence:
Let b be an arbitrary element of B. Since Dom(S) = B, so we can choose some $c\in C$ s.t. $(b,c)\in S$

Uniqueness:
Let b be an arbitrary element of B. Let c,d be arbitrary elements of C s.t. $(b,c)\in S$ and $(b,d)\in S$. Since Ran(R) = B, so we can choose some $a\in A$ s.t. $(a,b)\in R$. Then $(a,c)\in S\circ R$ and $(a,d)\in S\circ R$. So c = d.

Hence S:B -> C

(b) Here is such an example.
A = {1}
B = {1,2}
C = {3}

S = {(1,3),(2,3)}
R = {(1,1),(1,2)}
$S\circ R$ = {(1,3)}


Ex-11:
(a) Suppose S is reflexive. Let x be an arbitrary element of A. $f\left(x\right)\in B$, so $\left(f\right(x),(f\left(x\right)\left)\right)\in S$ because S is reflexive. Then $(x,x)\in R$. Since x is arbitrary, so R is reflexive.

Using similar arguments, we can prove part(b) and part(c) also


Ex-12:
(a) No, Here is the counterexample.
A = {1,2}
B = {3,4,5}
f = {(1,3),(2,4)}
R = {(1,1),(2,2),(1,2)}

S = {(3,4),(3,3),(4,4)}, Its not reflexive as $(5,5)\notin S$

(b) Yes, Proof:
Suppose R is symmetric. Let (x,y) be arbitrary element of S, then we can choose u and v in A s.t.
f(u) = x
f(v) = y and $(u,v)\in R$.
Since R is symmetric, so $(v,u)\in R$ and hence $(y,x)\in S$. Since (x,y) is arbitrary, so S is symmetric.

(c) Yes, Proof:
Suppose R is transitive. Let (x,y) and (y,z) be arbitrary ordered pairs in B x B s.t. $(x,y)\in S$ and $(y,z)\in S$. Then we can choose u,v,w in A s.t.
f(u) = x
f(v) = y
f(w) = z and $(u,v)\in R$ and $(v,w)\in R$.
Since R is transitive, so $(u,w)\in R$ and hence $(x,z)\in S$. Thus S is transitive.

Note: The book solution says its not and counterexample given is wrong as R given in the example is not transitive because R = {(1,2),(3,4)} and $(1,4)\notin R$.


Ex-13:
(a) Suppose R is reflexive. Let f be an arbitrary function in $F$ and let x be an arbitrary element of A. Then $f\left(x\right)\in B$. Since R is reflexive, so $\left(f\right(x),f(x\left)\right)\in R$. Since x is arbitrary so $(f,f)\in S$. And since f is arbitrary, so S is reflexive.

(b) Suppose R is symmetric. Let (f,g) is an arbitrary ordered pair in S. Let x be an arbitrary element of A. Then $\left(f\right(x),g(x\left)\right)\in R$. Since R is symmetric, so $\left(g\right(x),f(x\left)\right)\in R$. Then $(g,f)\in S$. Since (f,g) is arbitrary so S is symmetric.

(c) Suppose R is transitive. Let (f,g) and (g,h) be ordered pairs in S. Let x be an arbitrary element of A. Then $\left(\right(f\left(x\right),g\left(x\right))\in R$ and $\left(g\right(x),h(x\left)\right)\in R$. Since R is transitive, so $\left(f\right(x),h(x\left)\right)\in R$. Then $(f,h)\in S$. Since (f,g) and (g,h) are arbitrary so S is transitive.


Ex-14:
(a) Let x be an arbitrary element of A.
Then, $(f\circ g)$(x) = f(g(x)) = a = f(x).

(b) Let x be an arbitrary element of A. Then $(f\circ g)$(x) = f(g(x)). Since $(f\circ g)$ = f, so f(g(x)) = f(x). Since g is arbitrary, so it can be a constant function. Let g(x) = b. Then f(b) = f(x). Since f(b) is constant and x is arbitrary, so f is a constant function.


Ex-15:
(a) Since $\forall x>0(\mid x\mid =x)$, so $(\mid x\mid ,x)\in R$. Thus $(f,g)\in R$.

(b) First, we prove that R is reflexive on $F$.
Since for any arbitrary x in A, any arbitrary function f in $F$, f(x) = f(x). Then $(f,f)\in R$. Since f is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on $F$.
Let (f,g) be an arbitrary ordered pair in R. Then we can choose an $a\in R$ s.t. for every x > a, f(x) = g(x). Then g(x) = f(x) also. Then $(g,f)\in R$. Since (f,g) is arbitrary, so R is symmetric.

Third, we prove that R is transitive on $F$.
Let (f,g) and (g,h) be arbitrary ordered pairs in R. Then we can choose real numbers a and b s.t. for every
x > a, f(x) = g(x) and
x > b, g(x) = h(x).

Let c = maximum of a and b. Then for every x > c, f(x) = g(x) = h(x). Then $(f,h)\in R$. Since (f,g) and (g,h) are arbitrary, so R is transitive.

Hence R is equivalence relation on $F$.



Ex-16:
(a) Proof for $f\in O\left(g\right)$:
Let a = 3 and c = 8. Then for any x > a = 3,
|f(x)| = |7x + 3| = 7x + 3 < 7x + x = 8x < 8$x^2$ = c|g(x)|
Hence $f\in O\left(g\right)$

Proof for $g\notin O\left(f\right)$:
We'll prove it by contradiction. Assume $g\in O\left(f\right)$. Then we can choose some $a\in z^{+}$ and $c\in R^{+}$ s.t.for every positive integer x > a, $\mid x^2\mid \le c\mid 7x+3\mid$. For a x greater than a and 10c,
We have x > 10c
=> $x^2$ > 10cx ...(i)

Since $\mid x^2\mid \le c\mid 7x+3\mid$
=> $x^2\le c\mid 7x+3x\mid$
=> $x^2\le 10cx$ ...(ii)

clearly there is a contradiction between eq (i) and (ii), so our assumption is correct and $g\notin O\left(f\right)$

(b) First, we prove that S is reflexive in $F$.
For any arbitrary function $f\in F$ and for any arbitrary x, clearly |f(x)| = |f(x)|. So $f\in O\left(f\right)$. Then $(f,f)\in S$. Since f is arbitrary, so S is reflexive.

Second, we prove that S transitive in $F$.
Let (f,g) and (g,h) be two arbitrary elements in S. Then we can choose some positive integers a,b and positive real numbers c,d s.t.
$\forall x>a(\mid f(x)\mid \le c\mid g(x)\mid )$ and
$\forall x>b(\mid g(x)\mid \le d\mid h(x)\mid )$

Let e be the maximum of a and b. Let x be an arbitrary integer s.t. x > e. Then
$\mid f\left(x\right)\mid \le c\mid g\left(x\right)\mid$ and
$\mid g\left(x\right)\mid \le d\mid h\left(x\right)\mid$

Then $\mid f\left(x\right)\mid \le cd\mid h\left(x\right)\mid$. Since x is arbitrary, so $f\in O\left(h\right)$. Thus $(f,h)\in S$. Since (f,g) and (g,h) are arbitrary, so S is transitive.

Hence S is a preorder.

(c) Since $f_1\in O\left(g\right)$, so we can choose some $a\in Z^{+}$ and $c\in R^{+}$ s.t. $\forall x>a(\mid f_1(x)\mid \le c\mid g(x)\mid )$.
Since $f_2\in O\left(g\right)$, so we can choose some $b\in Z^{+}$ and $d\in R^{+}$ s.t. $\forall x>b(\mid f_2(x)\mid \le d\mid g(x)\mid )$.

Let e be the maximum of a and b. Then for any arbitrary positive integer x > e,
|f(x)|
= $\mid s{f}_1\left(x\right)+t{f}_2\left(x\right)\mid$ (using triangle inequality)
$\le s\mid f_1\left(x\right)\mid +t\mid f_2\left(x\right)\mid$
$\le c\mid g\left(x\right)\mid +d\mid g\left(x\right)\mid$ = $(c+d)\mid g\left(x\right)\mid$

Thus $f\in O\left(g\right)$.


Ex-17:
(a) First, we prove that R is reflexive on A.
Let x be an arbitrary element of A. Then g(x) = g(x). Then $(x,x)\in R$. Since x is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on A.
Let (x,y) be arbitrary element of R. Then g(x) = g(y). Then g(y) = g(x). Then $(y,x)\in R$. Since (x,y) is arbitrary, so R is symmetric.

Third, we prove that R is transitive on A.
Let (x,y) and (y,z) be arbitrary elements of R. Then g(x) = g(y) = g(z). Then $(x,z)\in R$. Since (x,y) and (y,z) are arbitrary, so R is transitive.

Hence R is equivalence relation on A.

(b) ($\to$) Let (x,y) be arbitrary element of R. Since R is equivalence relation, hence symmetric. Then $(y,x)\in R$. So $[x{]}_R=[y{]}_R$. Then g(x) = g(y). Since (x,y) is arbitrary so $R\subseteq \left\{\right(x,y)\in AxA\mid g(x)=g(y\left)\right\}$.
($\leftarrow$) Let (x,y) be arbitrary element of {$(x,y)\in AxA\mid g\left(x\right)=g\left(y\right)$}. Then g(x) = g(y). Then $[x{]}_R=[y{]}_R$. Then $(x,y)\in R$. Since (x,y) is arbitrary so $\left\{\right(x,y)\in AxA\mid g(x)=g(y\left)\right\}\subseteq R$

Hence R = {$(x,y)\in AxA\mid g\left(x\right)=g\left(y\right)$}


Ex-18:
(a)Existence:
Let us consider h = {$(X,y)\in A/RxB\mid \exists x\in X\left(f\right(x)=y)$}

clearly $\left(\right[x{]}_R,x)\in h$ as f(x) = f(x)

Uniqueness:
Let say there exists another function g s.t. g($[x{]}_R$) = f(x).
Let (X,y) be arbitrary element of g. Since Dom(g) = A/R. So we can choose some $x\in A$ s.t. $[x{]}_R=X$ and then $y=f\left(x\right)$. Then $(X,y)\in h$, where h is choosen above. so, $g\subseteq h$. Also, clearly using the similar argument $h\subseteq g$. So h = g. hence h is unique.

(b) Let x,y be arbitrary elements of A s.t. xRy. Since R is symmetric, so yRx also. Hence $[x{]}_R=[y{]}_R$. Then $h[x{]}_R=h[y{]}_R$. Then f(x) = f(y). Since x and y are arbitrary, so we can say that $\forall x\in A\forall y\in A(xRy\to f(x)=f(y\left)\right)$


Ex-19:
(a) Assume a function f s.t. f(x) = $[x^2{]}_R$
Let (x,y) be arbitrary element of R.
Then x $\equiv$ y(mod m)
so, we can choose some $k\in Z$ s.t.
x - y = km
=> x = y + km
=> $x^2=y^2+k^2{m}^2+2ykm$
=> $x^2-y^2=m(k^{2}m+2yk)$

Since $(k^{2}m+2yk)$ is also an integer, so $x^2\equiv y^2$(mod m). Thus $(x^2,y^2)\in R$. Since R is equivalence relation, so $[x^2{]}_R=[y^2{]}_R$. So f(x) = f(y). Since x and y are arbitrary so f is compatible with R.

So using the result of Ex-18(a), we can say that there exists an unique function h s.t. h($[x{]}_R$) = f(x) = $[x^2{]}_R$

(b) We will prove it by contradiction. Assume there exists a function h:Z/R -> Z/R s.t. h($[x{]}_R$) = $[2^x{]}_R$.
Let (x,y) be arbitrary element in R. Then $[x{]}_R=[y{]}_R$. Then $h\left(\right[x{]}_R)=h(\left[y{]}_R\right)$. Then $[2^x{]}_R=[2^y{]}_R$. Then $(2^x,2^y)\in R$.
Then $2^x\equiv 2^y$(mod m)

So we can choose an integer k s.t.
$2^x-2^y$ = km ...(i)

Since $(x,y)\in R$ also so x $\equiv$ y(mod m). Hence we can choose an integer l s.t. (x - y) = lm ...(ii)

From eq(i) and eq(ii) we get
$\frac{2^x-2^y}{x-y}$ = $\frac{k}{l}$

RHS is a constant, but LHS can't be, which is a contradiction and hence such a function as assumed can not exist.