how to prove it - a retrospection

I just finished working through velleman's how to prove it. All of my notes and solution to exercises can be found here. After reading it, here is what I think.

What I expected before I started reading it?
I expected to learn how mathematicians *think* when they encounter a conjecture. And, hoped that this would make it easy for me to read/understand any proof based books like cormen et al.

What I found?
Essential logic theory, A *solid* understanding of the abstract *structures* used in proofs and how these structures come from logic. You learn set, relations and functions for free as side effects :)

It helped a lot to have some understanding of (propositional)logic and quantifiers before I started reading this book. After working through this book when you will look at any proof, you will first understand the abstract structure behind the proof(in fact you'll just get it without even thinking about it) and then understand the specific details of the particular proof.

In short, I'm glad I read it. Thanks to Ravi for pointing me to it.

how to prove it - ch6, sec6.5(Closures Again) ex

Ex-1:
(a) Prove that $F \neq \emptyset$.
Its clear that $B \subseteq A$ and $A \subseteq A$ and also A is closed under f, hence $A \in F$. So $F \neq \emptyset$

Prove that $\cap F$ is closure of B under f.

Step-I: Prove that $B \subseteq \cap F$
Since for every $C \in F$, $B \subseteq C$. Hence $B \subseteq \cap F$

Step-II: Prove that $\cap F$ is closed under f.
Let x be an arbitrary element of $\cap F$. Let C be arbitrary element of $F$. Then $x \in C$ and hence $f(x) \in C$. Since C is arbitrary, so $\forall C \in F f(x) \in F$ and hence $f(x) \in \cap F$. Thus $\cap F$ is closed under f.

Step-III: $\cap F$ is smallest set closed under f s.t. B is its subset.
Let C be some set s.t. C is closed under f and $B \subseteq C$. Then $C \in F$ and hence $\cap F \subseteq C$. So $\cap F$ is indeed the smallest.

From Step I, II and III its clear that $\cap F$ is closure of B under f.

(b) Let C = $\cup_{n \in Z+} B_n$

Step-I: prove that $B \subseteq C$
Since $B_1 = B$ and $B_1 \subseteq C$, hence $B \subseteq C$

Step-II: prove that C is closed under f
Let x be arbitrary element of C. Then we can choose some positive integer n s.t. $x \in B_n$. Then $f(x) \in B_{n+1}$. Then $f(x) \in C$. Thus C is closed under f.

Step-III: prove that C is smallest set closed under f s.t. B is its subset
Let D be some other set s.t. $B \subseteq D$ and D is closed under f. We'll prove by induction that for any positive number n, $B_n \subseteq D$ and hence $C \subseteq D$.

Base case: for n = 1
$B_1 = B$, so $B_1 \subseteq D$

Induction step: Suppose n is arbitrary positive integer and $B_n \subseteq D$.

Let y be arbitrary element of $B_{n+1}$. Then we can choose some $x \in B_n$ s.t. f(x) = y. Since $B_n \subseteq D$, so $x \in D$ and hence $f(x) \in D$. Then $y \in D$. Since y is arbitrary, so $B_{n+1} \subseteq D$.

From the three steps above, its proven that C is closure of B under f.


Ex-2: Using the terminology from ex-1, B = {0}.
Then, $B_1$ = B = {0}
$B_2$ = {f(0)} = {1}
$B_3$ = {f(1)} = {2}
$B_4$ = {f(2)} = {3}
...

closure of {0} under f is $\cup_{n \in Z+}B_n$ = {0,1,2,3,...} = Set of all natural numbers.


Ex-3: We'll imitate the reasoning followed in ex-1(a).

Let $H$ = {C | $B \subseteq C \subseteq A$ and $\forall f \in F$, C is closed under f}

Step-I: prove that $H \neq \emptyset$
$B \subseteq A$ and $A \subseteq A$ and for every function f in $F$, A is closed under f. Hence $A \in H$. Thus $H \neq \emptyset$

So, $\cap H$ is defined. We will prove that $\cap H$ is closure of B under $F$.

Step-II: Prove that $B \subseteq \cap H$
Since for every $C \in H$, $B \subseteq C$. Hence $B \subseteq \cap H$

Step-III: Prove that $\cap H$ is closed under $F$.
Let x be an arbitrary element of $\cap H$. Let C be arbitrary element of $H$. Then $x \in C$. Let f be arbitrary element of $F$. Then $f(x) \in C$. Since C is arbitrary, so $\forall C \in H f(x) \in H$ and hence $f(x) \in \cap H$. Thus $\cap H$ is closed under f. Since f is arbitrary, so $\cap H$ is closed under $F$.

Step-IV: $\cap H$ is smallest set closed under $F$ s.t. B is its subset.
Let C be some set s.t. C is closed under $F$ and $B \subseteq C$. Then $C \in H$ and hence $\cap H \subseteq C$. So $\cap H$ is indeed the smallest.

From Step I, II, III and IV its clear that $\cap H$ is closure of B under $F$. Hence closure of B under $F$ exists.


Ex-4,5,6: I could not solve ex-4 and 5,6 are dependant on it. TODO


Ex-7: We'll use induction to prove it.

Base case: n = 1, Since $R \subseteq S$, so $R^1 \subseteq S^1$

Induction step: let n be arbitrary positive integer and $R^n \subseteq S^n$

Now, Let (x,y) be arbitrary element of A X A s.t. $(x,y) \in R^{n+1}$

Since $R^{n+1}$ = $R^n \circ R$, so $(x,y) \in R^n \circ R$. Then we can choose some $z \in A$ s.t. $(x,z) \in R$ and $(z,y) \in R^n$. Then $(x,z) \in S$ and $(z,y) \in S^n$. Then $(x,y) \in S^n \circ S$. Then $(x,y) \in S^{n+1}$. Since (x,y) is arbitrary, so $R^{n+1} \subseteq S^{n+1}$.


Ex-8:
(a) Let n be arbitrary positive integer.
$R \cap S \subseteq R$, so using result of ex-7, $(R \cap S)^n \subseteq R^n$. Similarly, $(R \cap S)^n \subseteq S^n$. Thus $(R \cap S)^n \subseteq R^n \cap S^n$. However, the two are not equal as is evident from following counterexample.
A = {1,2,3,4}
R = {(1,2), (2,4)}
S = {(1,3), (3,4)}

Then $(R \cap S)^2 = \emptyset$ and $R^2 \cap S^2$ = {(1,4)}

(b) $R \subseteq (R \cup S)$, so $R^n \subseteq (R \cup S)^n$. Similarly, $S^n \subseteq (R \cup S)^n$. Thus $R^n \cup S^n \subseteq (R \cup S)^n$. However, the two are not equal as is evident from following counterexample.
A = {1,2,3,4}
R = {(1,2), (2,4)}
S = {(2,3), (3,4)}

$R^2$ = {(1,4)}
$S^2$ = {(2,4)}

$R^2 \cup S^2$ = {(1,4), (2,4)}

$R \cup S$ = {(1,2), (2,4), (2,3), (3,4)}
$(R \cup S)^2$ = {(1,4),(2,4),(1,3)}

clearly the two are not equal.


Ex-9:
(a) Let d(a,b) = n and d(b,c) = m. Then
$(a,b) \in R^n$ and
$(b,c) \in R^m$

Then $(a,c) \in R^m \circ R^n$. Then $(a,c) \in R^{m+n}$. Hence d(a,c) $\leq$ (m+n) = d(a,b) + d(b,c)

(b) TODO


Ex-10:
(a) We'll prove it by induction.

Base case: n = 1
($\rightarrow$) Let (a,b) be arbitrary element of $R^1$ that is R. Let us define a function f s.t. f(0) = a and f(1) = b. Clearly, f is R-path from a to b of length 1. So it exists
($\leftarrow$) Let f be an R-path from a to b of length 1. Then $(f(0),f(1)) \in R$. Thus $(a,b) \in R$.

Induction step: Let n be a positive integer and $R^n$ = {$(a,b) \in AxA$ | there is an R-path from a to b of length n}

($\rightarrow$) Let (a,b) be arbitrary element of $R^{n+1}$. Then $(a,b) \in R \circ R^n$. Then we can choose some c s.t. $(a,c) \in R^n$ and $(c,b) \in R$.
By induction hypothesis we can choose f, a R-path from a to c of length n. Then f(0) = a and f(n) = c. Then $f \cup${(n+1),b} is an R-path from a to b of length n+1.
($\leftarrow$) Let f be an R-path from a to b of length n+1. Let f(n) = c. Then $f \setminus${(n+1,b)} is an R-path from a to c of length n. So, by induction hypothesis, $(a,c) \in R^n$. Also, $(f(n),f(n+1)) \in R$, so $(c,b) \in R$. Thus $(a,b) \in R \circ R^n$. Hence $(a,b) \in R^{n+1}$

(b) From theorem 6.5.2, $S = \cup_{n \in Z+} R^n$

($\rightarrow$) Let (a,b) be arbitrary element of S. Then we can choose some positive integer n s.t. $(a,b) \in R^n$. Then, by result proved in part(a), there exists an R-path from a to b of length n.

($\leftarrow$) Let n be arbitrary positive integer. Let f be an R-path from a to b of length n. Then $(a,b) \in R^n$. Then $(a,b) \in S$


Ex-11:
(a) We'll prove it by induction.

Base case: n = 1, Let (a,b) be arbitrary element of $R^1 \setminus i_A$. Then $(a,b) \in R$ and $a \neq b$. Let us define f s.t. f(0) = a and f(1) = b. clearly f is an R-path from a to b of length 1 and also f is one-to-one

Induction step: Let n be arbitrary positive integer. Let $R^n \setminus i_A$ = {$(a,b) \in AxA$ | there is a simple R-path from a to b of length atmost n}


Let (a,b) be arbitrary element of $R^{n+1} \setminus i_A$. Then $(a,b) \in R^{n+1}$ and $a \neq b$. then $(a,b) \in R^1 \circ R^n$. Then we can choose some $c \in A$ s.t. $(a,c) \in R^n$ and $(c,b) \in R$. By induction hypothesis, we can find some simple R-path from a to c of length m s.t. $m \leq n$.
Now let us define g = f $\cup$ {(m+1,b)}. Consider following cases..

case#1: $b \notin Ran(f)$
Then g is one-to-one and also a R-path from a to b of length m+1 and $(m+1) \leq (n+1)$

case#2: $b \in Ran(f)$
Then we can choose some $k \leq m$ s.t. f(k) = b. Let us define another function h s.t. h(x) = f(x) for {1,k}. Then h is one-to-one and an R-path from a to b of length k and $k \leq n+1$.

from both the cases, its clear that there exists a simple R-path from a to b of length atmost n+1.

(b) From theorem 6.5.2, S = $\cup_{n \in Z+} R^n$

($\rightarrow$) Let (a,b) be arbitrary element of $S \setminus i_A$. Then $(a,b) \in S$ and $a \neq b$. Then we can choose some positive integer n s.t. $(a,b) \in R^n$. Using result of part-a, there exists a simple R-path from a to b of length atmost n.

($\leftarrow$) Let f be a simple R-path from a to b of length n. Then f is one-to-one, and hence $f(0) \neq f(n)$ and hence $a \neq b$ and so $(a,b) \notin i_A$. Also from ex-10(a) $(a,b) \in R^n$ and hence $(a,b) \in S$. Since $(a,b) \in S$ and $(a,b) \notin i_A$, so $(a,b) \in S \setminus i_A$.


Ex-12:
(a) Since d(a,b) = n, so by definition of the distance as given in ex-9, $(a,b) \in R^n$ and there don't exist any number m smaller than n s.t. $(a,b) \in R^m$.
Also since $a \neq b$, so $(a,b) \notin i_A$. Then $(a,b) \in R^n \setminus i_A$. Then by result of ex-11(a) we can conclude that there is a simple R-path from a to b of length atmost n.
Now we will prove by contradiction that a simple R-path from a to b of length smaller than n can not exist and hence there is a simple R-path from a to b of length n.

Assume there is a simple R-path from a to b of length m and m < n. Then by ex-10(a), $(a,b) \in R^m$. But this is a contradiction as d(a,b) = n. Hence there is a simple R-path from a to b of length n.

(b) As d(a,a) = n, so $(a,a) \in R^n$. Then by ex-10(a), there is a R-path, let us call if f, from a to b of length n.
Then f(0) = a = f(n).

Let i and j be arbitrary positive integers smaller than n s.t. f(i) = f(j) = c where $c \in A$.

Since f(0) = a and f(i) = c, clearly f is an R-path of length i from a to c and hence by ex-10(a), $(a,c) \in R^i$.
Let us define h(x) = f(x+j). Then h(0) = f(j) = c and h(n-j) = f(n) = a. Clearly h is an R-path from c to a of length n-j and hence again by ex-10(a), $(c,a) \in R^{n-j}$
Thus $(a,a) \in R^{n-j} \circ R^i$. And then $(a,a) \in R^{n-j+i}$. Since d(a,a) = n, so $(n-j+i) \geq n$. Then $i \geq j$.

Using above reasoning by switching roles of f(i) and f(j), we can come to the conclusion that $j \geq i$.

Since $i \geq j$ and $j \geq i$, so $i = j$. Since i and j are arbitrary positive integers smaller than n, so $\forall i < n \forall j < n (f(i)=f(j) \rightarrow i=j)$


Ex-13: Let $f:j_n \rightarrow A$ be a simple R-path of length n where $j_n$ = {0,1,2,3,...,n}

Then size of Dom(f) = Size of $j_n$ = n+1
size of Ran(f) = size of A = m

Since f is one-to-one, so $n+1 \leq m$. Then $n \leq (m-1)$ . Thus n can atmost be m-1. Hence maximum possible length of a simple R-path is m-1.

Now we will prove that, for any n > m we can choose some l < m s.t. $R^n \subseteq R^l$.
Let (a,b) be arbitrary element of $R^n$. Let d(a,b) = l. Then by ex-12(a), there is a simple R-path from a to b of length l. Then l < m. Since d(a,b) = l, hence $(a,b) \in R^l$. Since (a,b) is arbitrary, so $R^n \subseteq R^l$
Since n is arbitrary, so $\forall n > m \exists l < m (R^n \subseteq R^l)$

So, $\cup \{R^n | n > m\} \subseteq \cup \{R^n | 1 \leq n \leq m\}$

Then S = $\cup \{R^n | n > 1\}$ = $\cup \{R^n | 1 \leq n \leq m\}$


Ex-14: Base case: n = 1, x = (1+1)! + 2 = 2! + 2 = 4
i can only be 0 in this case and clearly (i+2) = 2 divides (x+i) = 4

Induction step: Suppose n is an arbitrary positive integer, define x = (n+1)! + 2, s.t. for every i s.t. $0 \leq i \leq n-1$, (i+2)|(x+i).

Let y = (n+2)! + 2. Let us consider following possible set of cases.

Case#1: i = n
Then (i+2) = (n+2) and (y+i) = (n+2)! + (n+2) = (n+2)[(n+1)!+1]. clearly (i+2)|(y+i)

Case#2: i < n
y+i = (n+2)! + 2 + i
= (n+2).(n+1)! + (2+i)
= (n+2)[(n+1)! + (2+i) - (2+i)] + (2+i)
= (n+2)[(n+1)! + (2+i)] - (n+2)(2+i) + (2+i)
= (n+2)(x+i) - [(n+2) - 1](2+i)
= (n+2)(x+i) - (n+1)(i+2)

by induction hypothesis, (i+2)|(x+i) and also (i+2)|[(n+1)(i+2)].

Thus (i+2)|(y+i)

Its clear from above cases that for every i s.t. $0 \leq i \leq n$, (i+2)|(y+i)

how to prove it - ch6, sec6.4(Strong Induction) ex

Strong induction is a variant of mathematical induction that is used to prove the goals of the form $\forall n \in N P(n)$.

To Prove a goal of the form $\forall n \in N P(n)$
Prove that $\forall n [(\forall k < n P(k)) \rightarrow P(n)]$, where n and k both are natural numbers. Note that no base case is necessary in a proof by strong induction.

Why it works?
If we proved $\forall n [(\forall k < n P(k)) \rightarrow P(n)]$. Then plugging n = 0, we get $(\forall k < 0 P(k)) \rightarrow P(0)$. Now, $\forall k < 0 P(k)$ is vacuously true as there are no natural numbers smaller than 0. Hence P(0) is true. Now keep applying the strong induction hypothesis to see that P(n) is true for any natural number.

Note:
I highly recommend that base case should atleast be checked if not proved. Because, not checking the base case, can lead to false proofs as following. (I'm taking ex-17(a) from section-6.1)

Q. Can you point out the error in following proof?

Theorem: Prove that for all $n \in N$, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Proof:

Let n be arbitrary natural number. Suppose, for all natural numbers k smaller than n,
$1.3^0 + 3.3^1 + 5.3^2 + .. + (2k+1)3^k = k3^{k+1}$

Since (n-1) < n, Then it follows from our assumption that
$1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1} = (n-1)3^n$

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

Hence, by the assumptions of strong induction, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Ans. To apply the induction hypothesis "for all natural numbers k smaller than n ..." to n-1, you need not only that (as you said) n-1 < n but also that n-1 is a natural number. That fails when n=0, so your argument doesn't cover the case n=0. – Andreas Blass [http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/]

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


Ex-1

Givens:
$\forall n [(\forall k < n P(k)) \rightarrow P(n)]$
Q(n) = $\forall k < n P(k)$

(a) ($\rightarrow$) Suppose $\forall n Q(n)$. Let n be arbitrary. It follows from our assumption that Q(n+1). Then $\forall k < (n+1) P(k)$. In particular we can choose k = n to see that P(n). Since n is arbitrary, so $\forall n P(n)$

($\leftarrow$) Suppose $\forall n P(n)$. So for any n, for every k < n, P(k). Then $\forall k < n P(k)$. Then Q(n). Since n is arbitrary, so $\forall n Q(n)$

(b) Base case: For n = 0, Q(0) = $\forall k < 0 P(k)$ , since there is no k smaller than 0 so this statement is vacuously true.

Induction step: Let n be arbitrary natural number and Q(n). Then $\forall k < n P(k)$. Then it follows from the givens that P(n). Thus $\forall k < (n+1) P(k)$. So Q(n+1).


Ex-2 Let q be arbitrary natural number. Suppose, for all k < q, $\lnot \exists p \in N (\frac{p}{k} = \sqrt{2})$.

Assume, we can choose a natural number p s.t. $\frac{p}{q} = \sqrt{2}$. Then, following the logic used in theorem 6.2.5, we come to the conclusion that p and q both are even. Now, let us say p' = p/2 and q' = q/2. Then, $\frac{p'}{q'} = \sqrt{2}$. Since q' < q, so this contradicts with our induction hypothesis. Hence we can not choose such a natural number p. Hence $\forall k < (q+1) [\lnot \exists p \in N (\frac{p}{k} = \sqrt{2})]$. Since q is arbitrary, so $\sqrt{2}$ is irrational.


Ex-3
(a) Assume $\sqrt{6}$ is rational. Let S = { $q \in Z+ | \exists p \in Z+ (\frac{p}{q} = \sqrt{6})$ }. Then $S \neq \emptyset$. So, using well-ordering-property we can choose the smallest element of S, say q, and a positive integer p s.t. $\frac{p}{q} = \sqrt{6}$.
Then, $\frac{p^2}{q^2} = 6$
=> $p^2 = 6q^2$

so $p^2$ is even and hence p is even, then we can choose a p' such that p = 2p'.

Then, ${(2p')}^2 = 6q^2$
=> $4{(p')}^2 = 6q^2$
=> $2{(p')}^2 = 3q^2$

Then $3q^2$ is even and hence $q^2$ is even and hence q is even, then we can choose a q' such that q = 2q'.

Also, since $\frac{p}{q} = \sqrt{6}$
=> $\frac{p'}{q'} = \sqrt{6}$

so clearly $q' \in S$ and also $q' < q$. This contradicts with the assumption that q is smallest element of S and hence $\sqrt{6}$ is irrational.

(b) Assume $\sqrt{2} + \sqrt{3}$ is rational. Then we can choose positive integers p and q s.t.
$\frac{p}{q} = \sqrt{2} + \sqrt{3}$

On squaring both sides we get

$\frac{p^2}{q^2} = 2 + 3 + 2\sqrt{6}$
=> $\frac{p^2}{q^2} = 5 + 2\sqrt{6}$
=> $\sqrt{6} = \frac{p^2 - 5q^2}{2q^2}$

Then , $\sqrt{6}$ is rational. this is a contradiction with result proved in part(a). Hence $\sqrt{2} + \sqrt{3}$ is irrational.


Ex-4 Let n be arbitrary natural number s.t. $n \geq 12$. Suppose for every k < n, there is some combination of blue and red beads that is worth k credits.

Let us consider the following cases.

Case#1: $n \geq 15$
Then $(n-3) \geq 12$ and $(n-3) < n$. It follows from induction hypothesis that we can choose b blue and r red beads s.t. 3b + 7r = (n-3).
Then n = 3(b+1) + 7r.

Case#2: n = 12
n = 3(4) + 0(7)

Case#3: n = 13
n = 3(2) + 7(1)

Case#4: n = 14
n = 3(0) + 7(2)

Its clear from all these cases that for every $n \geq 12$ we can choose some combination of red and blue beads that worth n credits.


Ex-5 Let n be arbitrary natural number s.t. $n \geq 1$. Suppose for every k < n, $x^k + \frac{1}{x^k}$ is integer.

Now, from induction hypothesis, $x^{n-1} + \frac{1}{x^{n-1}}$ and $x + \frac{1}{x}$, both are integers.

Hence $(x^{n-1} + \frac{1}{x^{n-1}})(x + \frac{1}{x})$ is an integer
=> $x^n + \frac{1}{x^{n-2}} + x^{n-2} + \frac{1}{x^n}$ is an integer
=> $(x^n + \frac{1}{x^n}) + (x^{n-2} + \frac{1}{x^{n-2}})$ is an integer

Since (n-2) < n, so $(x^{n-2} + \frac{1}{x^{n-2}})$ is an integer. And hence, $x^n + \frac{1}{x^n}}$ is also an integer.


Ex-6
(a) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_i = F_{k+2} - 1$

Now, $\sum_{i=0}^{n} F_i$
= $(\sum_{i=0}^{n-1} F_i) + F_n$ (apply induction hypothesis to get...)
= $F_{n+1} - 1 + F_n$
= $F_{n+1} + F_n - 1$
= $F_{n+2} - 1$

(b) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} {(F_i)}^2 = F_kF_{k+1}$

Now, $\sum_{i=0}^{n} {(F_i)}^2$
= $(\sum_{i=0}^{n-1} {(F_i)}^2) + {(F_n)}^2$ (apply induction hypothesis to get...)
= $F_{n-1}F_n + {(F_n)}^2$
= $F_n(F_{n-1} + F_n)$
= $F_nF_{n+1}$

(c) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_{2i+1} = F_{2k+2}$

Now, $\sum_{i=0}^{n} F_{2i+1}$
= $(\sum_{i=0}^{n-1} F_{2i+1}) + F_{2n+1}$ (apply induction hypothesis to get...)
= $F_{2(n-1)+2} + F_{2n+1}$
= $F_{2n} + F_{2n+1}$
= $F_{2n+2}$

(d) Scratchwork:
$\sum_{i=0}^{0} F_{2i} = 0 = F_{2.0 + 1} - 1$
$\sum_{i=0}^{1} F_{2i} = 1 = F_{2.1 + 1} - 1$
$\sum_{i=0}^{2} F_{2i} = 4 = F_{2.2 + 1} - 1$
$\sum_{i=0}^{3} F_{2i} = 12 = F_{2.3 + 1} - 1$
$\sum_{i=0}^{4} F_{2i} = 33 = F_{2.4 + 1} - 1$

easy guess... $\sum_{i=0}^{n} F_{2i} = F_{2n+1} - 1$

Proof:
Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_{2i} = F_{2k+1} - 1$

Now, $\sum_{i=0}^{n} F_{2i}$
= $\sum_{i=0}^{n-1} F_{2i} + F_{2n}$ (apply induction hypothesis to get...)
= $(F_{2(n-1) + 1} - 1) + F_{2n}$
= $F_{2n-1} + F_{2n} - 1$
= $F_{2n+1} - 1$


Ex-7
(a) Let m be an arbitrary natural number greater than or equal to 1. Let n be an arbitrary natural number. Suppose for every k < n, $F_{m+k} = F_{m-1}F_k + F_mF_{n+1}$

Let us consider following cases.

Case#1: n = 0
Then LHS = $F_{m+0} = F_m$
RHS = $F_{m-1}F_0 + F_mF_{0+1}$ = $0 + F_mF_1$ = $F_m$
clearly LHS = RHS

Case#2: n = 1
Then LHS = $F_{m+1}$
RHS = $F_{m-1}F_1 + F_mF_2$ = $F_{m-1} + F_m$ = $F_{m+1}$
clearly LHS = RHS

Case#3: $n \geq 2$
$F_{m+n}$
= $F_{m+n-1} + F_{m+n-2}$ (apply induction hypothesis to get...)
= $(F_{m-1}F_{n-1} + F_mF_n) + (F_{m-1}F_{n-2} + F_mF_{n-1})$
= $F_{m-1}(F_{n-1} + F_{n-2}) + F_m(F_n + F_{n-1})$
= $F_{m-1}F_n + F_mF_{n+1}$

clearly, by strong induction, $F_{m+n} = F_{m-1}F_n + F_mF_{n+1}$

(b) Let m be an arbitrary natural number greater than or equal to 1. Let n be an arbitrary natural number greater than or equal to 1. Suppose for every k < n, $F_{m+k} = F_{m+1}F_{k+1} + F_{m-1}F_{n-1}$

Let us consider following cases.

Case#1: n = 2
LHS = $F_{m+2}$
RHS = $F_{m+1}F_3 - F_{m-1}F_1$ = $2F_{m+1} - F_{m-1}$ = $F_{m+1} + F_{m+1} - F_{m-1}$ = $F_{m+1} + F_m + F_{m-1} - F_{m-1}$ = $F_{m+1} + F_m$ = $F_{m+2}$
clearly, LHS = RHS

Case#2: n = 3
LHS = $F_{m+3}$
RHS = $F_{m+1}F_4 - F_{m-1}F_2$ = $3F_{m+1} - F_{m-1}$ = $2F_{m+1} + F_m + F_{m-1} - F_{m-1}$ = $2F_{m+1} + F_m$ = $F_{m+1} + F_{m+2}$ = $F_{m+3}$
clearly, LHS

Case#3: n > 3
$F_{m+n}$
= $F_{m+n-1} + F_{m+n-2}$ (apply induction hypothesis on both terms)
= $(F_{m+1}F_n - F_{m-1}F_{n-2}) + (F_{m+1}F_{n-1} - F_{m-1}F_{n-3})$
= $F_{m+1}(F_n + F_{n-1}) - F_{m-1}(F_{n-2} + F_{n-3})
= $F_{m+1}F_{n+1} - F_{m-1}F_{n-1}$

Its clearly from above 3 cases that for any natural number $n \geq 1$, $F_{m+n} = F_{m+1}F_{n+1} - F_{m-1}F_{n-1}$

(c) Let n be an arbitrary natural number. Suppose for every k < n, ${(F_k)}^2 + {(F_{k+1})}^2 = F_{2k+1}$

Let us consider following cases.

Case#1: n = 1
${(F_1)}^2 + {(F_2)}^2 = 1^2 + 1^2 = 1 + 1 = 2 = F_3 = F_{2(1)+1}$

Case#2: n = 2
${(F_2)}^2 + {(F_3)}^2 = 1^2 + 2^2 = 1 + 4 = 5 = F_5 = F_{2(2)+1}$

Case#3: n > 3
${(F_n)}^2 + {(F_{n+1})}^2$
= ${(F_{n-1} + F_{n-2})}^2 + {(F_n + F_{n-1})}^2$
= ${(F_{n-1})}^2 + {(F_{n-2})}^2 + 2F_{n-1}F_{n-2} + {(F_n)}^2 + {(F_{n-1})}^2 + 2F_nF_{n-1}$
= $({(F_{n-1})}^2 + {(F_{n-2})}^2) + ({(F_n)}^2 + {(F_{n-1})}^2) + 2(F_{n-1}F_{n-2} + F_nF_{n-1})$

In part(a) put m = n and n = n-2 to check that $F_{n-1}F_{n-2} + F_nF_{n-1} = F_{2n-2}$, so above term becomes...

= $({(F_{n-1})}^2 + {(F_{n-2})}^2) + ({(F_n)}^2 + {(F_{n-1})}^2) + 2F_{2n-2}$ (apply induction hypothesis to get)
= $(F_{2n-3}) + (F_{2n-1}) + 2F_{2n-2}$
= $(F_{2n-3} + F_{2n-2}) + (F_{2n-1} + F_{2n-2})$
= $F_{2n-1} + F_{2n}$
= $F_{2n+1}$

From above 3 cases, its clear that for all natural number n, ${(F_n)}^2 + {(F_{n+1})}^2 = F_{2n+1}$

(d) Let m be any arbitrary positive integer.

Let n be arbitrary positive integer and for every k < n, if m|k then $F_m|F_k$.

Now, let m|n. Then m = nk for some positive integer k.

Let us consider following possible cases

Case#1: k = 1
then m = n and clearly $F_m|F_n$

Case#2: k > 1
Then $F_n$
= $F_{km}$
= $F_{km - m + m}$
= $F_{m + (k-1)m}$ (apply part(a) result)
= $F_{m-1}F_{(k-1)m} + F_mF_{(k-1)m + 1}$

by induction hypothesis, $F_m |F_{(k-1)m}$. Hence $F_m |(F_{m-1}F_{(k-1)m})$. Also, $F_m|(F_mF_{(k-1)m + 1})$

So $F_m|F_n$

(e) Its trivial to prove the base cases with n = 1 and n = 2, I'm skiping them.

Let n be arbitrary natural number s.t. n > 2 and for every k < n,

$F_{2k-1} = \sum_{i=0}^{k-1} {2k-i-2}\choose{i}$ and
$F_{2k} = \sum_{i=0}^{k-1} {2k-i-1}\choose{i}$

Now, $F_{2n-1}$
= $F_{2n-2} + F_{2n-3}$
= $F_{2(n-1)} + F_{2(n-1)-1}$ (now apply induction hypothesis)
= $\sum_{i=0}^{n-2} {2(n-1)-i-1}\choose{i} + \sum_{i=0}^{n-2} {2(n-1)-i-2}\choose{i}$
= $\sum_{i=0}^{n-2} {2n-i-3}\choose{i} + \sum_{i=0}^{n-2} {2n-i-4}\choose{i}$

Let us look consider the 2nd term..
$\sum_{i=0}^{n-2} {2n-i-4}\choose{i}$ (let i = j-1)
= $\sum_{j=1}^{n-1}{2n-j-3}\choose{j-1}$ (let j = i)
= $\sum_{i=1}^{n-1}{2n-i-3}\choose{i-1}$

So, $F_{2n-1}$
= $\sum_{i=0}^{n-2} {2n-i-3}\choose{i} + \sum_{i=1}^{n-1}{2n-i-3}\choose{i-1}$
= $({2n-3}\choose{0} + \sum_{i=1}^{n-2} {2n-i-3}\choose{i}) + (\sum_{i=1}^{n-2}{2n-i-3}\choose{i-1} + {n-2}\choose{n-2})$
= $1 + \sum_{i=1}^{n-2} ({2n-i-3}\choose{i} + {2n-i-3}\choose{i-1}) + 1$
= $1 + \sum_{i=1}^{n-2} {2n-i-2}\choose{i} + 1$
= ${2n-0-2}\choose{0} + \sum_{i=1}^{n-2} {2n-i-2}\choose{i} + {2n-(n-1)-2}\choose{n-1}$
= $\sum_{i=0}^{n-1} {2n-i-2}\choose{i}$

Using similar steps we can get the result for $F_{2n}$


Ex-8:
(a) ($\rightarrow$) Suppose $a_0, a_1, a_2...$ is Gibonacci sequence.
clearly, $a_0 = c^0 = 1$
$a_1 = c^1 = c$
$a_2 = c^2$

It follows from the assumption that $a_2 = a_1 + a_0$
=> $c^2 = c + 1$
=> $c^2 - c - 1$

on solving above quadratic equation for c, we get that c is either $\frac{1 + \sqrt{5}}{2}$ or $\frac{1 - \sqrt{5}}{2}$

($\leftarrow$) Suppose c = $\frac{1 + \sqrt{5}}{2}$ or c = $\frac{1 - \sqrt{5}}{2}$, in both the cases
$c^2 = c + 1$
=> $c^n = c^{n-1} + c^{n-2}$
=> $a_n = a_{n-1} + a_{n-2}$

Hence $a_0, a_1, a_2...$ is Gibonacci sequence.

(b) Let n be an arbitrary natural number. Suppose for every k < n, $a_k = a_{k-1} + a_{k-2}$

Now, $a_{n-1} + a_{n-2}$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-1} + t{(\frac{1 - \sqrt{5}}{2})}^{n-1} + s{(\frac{1 + \sqrt{5}}{2})}^{n-2} + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}(\frac{1 + \sqrt{5}}{2} + 1) + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}(\frac{1 - \sqrt{5}}{2} + 1)$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}(\frac{3 + \sqrt{5}}{2}) + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}(\frac{3 - \sqrt{5}}{2})$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}{(\frac{1 + \sqrt{5}}{2})}^2 + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}{(\frac{1 - \sqrt{5}}{2})}^2$
= $s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$
= $a_n$

(c) Scratchwork:
$a_0 = s + t$ ...(i)

$a_1 = s(\frac{1 + \sqrt{5}}{2}) + t(\frac{1 - \sqrt{5}}{2})$
=> $2a_1 = (s+t) + \sqrt{5}(s-t)$
=> $s - t = \frac{2a_1 - a_0}{\sqrt{5}}$ ...(ii)

we can easily solve equation (i) and (ii) to get

s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$

Formal Proof:

Let s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$ and
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$

its trivial to check that
$a_n = s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$ holds true with chosen values of s and t for n = 0 and n = 1

from the result of part(b), $a_0, a_1, a_2, ...$ is Gibonacci sequence if $a_n = s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$ for any real numbers s and t so it should be true for chosen values of s and t also.

Hence such s and t indeed exist.


Ex-9: In ex-18(c), put $a_0 = L_0 = 2$ and $a_1 = L_1 = 1$

Use s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$ to get

s = 1 and t = 1

thus the required formula is... for $n \geq 2$, $L_n = {(\frac{1 + \sqrt{5}}{2})}^n + {(\frac{1 - \sqrt{5}}{2})}^n$

And, from the analysis of ex-8(c) itself this should be correct.


Ex-10: Scratchwork:
Let us imitate ex-8(a) and assume $a_n = c^n$

Since, $a_n = 5a_{n-1} - 6a_{n-2}$
=> $c^n = 5c^{n-1} - 6c^{n-2}$
=> $c^2 = 5c - 6$
=> $c^2 - 5c + 6 = 0$
=> $c^2 - 2c - 3c + 6 = 0$
=> $c(c-2) - 3(c-2) = 0$
=> $(c-2)(c-3) = 0$

Thus either c = 2 or c = 3

Now imitate ex-8(b) to guess that

$a_n = s2^n + t3^n$, where s and t are some real numbers.

Since $a_0 = -1$, so $s + t = -1$ ... eq(i)

and since $a_1 = 0$, so $2s + 3t = 0$ ... eq(ii)

on solving eq(i) and (ii) we get

s = -3 and t = 2

So, $a_n = 2.3^n - 3.2^n$

Formal Proof:

The formula is $a_n = 2.3^n - 3.2^n$

Suppose for every k < n, $a_k = 2.3^k - 3.2^k$

Let us consider following cases

Case#1: n = 0
RHS = $2.3^0 - 3.2^0 = 2 - 3 = -1 = a_0$ = LHS

Case#2: n = 1
RHS = $2.3^1 - 3.2^1 = 0 = a_1$ = LHS

Case#3: n > 1
$5a_{n-1} - 6a_{n-2}$ (apply induction hypothesis to get)
= $5(2.3^{n-1} - 3.2^{n-1}) - 6(2.3^{n-2} - 3.2^{n-2})$
= $10.3^{n-1} - 15.2^{n-1} - 4.3^{n-1} + 9.2^{n-1}$
= $6.3^{n-1} - 6.2^{n-1}$
= $2.3^n - 3.2^n$
= $a_n$


Ex-11: clearly $a_0 = 0 = F_0$, $a_1 = 1 = F_1$ and $a_2 = 1 = F_2$.

Now let n be arbitrary natural number. suppose for every k < n, $a_k = F_k$

Now, $a_n$
$\frac{1}{2}a_{n-3} + \frac{3}{2}a_{n-2} + \frac{1}{2}a_{n-1}$
= $\frac{a_{n-3} + 3a_{n-2} + a_{n-1}}{2}$ (apply induction hypothesis to get)
= $\frac{F_{n-3} + 3F_{n-2} + F_{n-1}}{2}$
= $\frac{(F_{n-3} + F_{n-2}) + 2F_{n-2} + F_{n-1}}{2}$
= $\frac{F_{n-1} + 2F_{n-2} + F_{n-1}}{2}$
= $\frac{2(F_{n-1} + F_{n-2})}{2}$
= $F_n$

so for all natural number n, $a_n = F_n$


Ex-12: Scratchwork:

we need to prove that # of elements in $P_n = F_{n+2} = F_{n+1} + F_n$
This gives a hint that # of elements $P_n$ = # of elements in $P_{n-1}$ + in $P_{n-2}$

Let us check that for some values of n

$P_1$ = {$\emptyset$,{1}} , size = 2
$P_2$ = {$\emptyset$,{1},{2}}, size = 3
$P_3$ = {$\emptyset$,{1},{2},{3},{1,3}}, size = 5
$P_4$ = {$\emptyset$,{1},{2},{3},{4},{1,3},{1,4},{2,4}}, size = 8

clearly our guess about the sizes seems to be true.

Also, now its easy to see that for all n > 2

$P_n$ = $P_{n-1} \cup $ {$X \cup \{n\} | X \in P_{n-2}$} (TODO: prove it)

Formal Proof:

# of elements in $P_1 = 2 = F_3$
# of elements in $P_2 = 3 = F_4$

Let n be arbitrary natural number greater than 2.

Then $P_n = P_{n-1} \cup $ {$X \cup \{n\} | X \in P_{n-2}$}

thus, # of elements in $P_n$ = # of element in $P_{n-1}$ + in $P_{n-2}$ = $F_{n+1} + F_n$ = $F_{n+2}$

Hence, for any natural number n s.t. $n \geq 1$, # of elements in $P_n$ = $F_{n+2}$


Ex-13:
(a) Let us consider both the possible cases:
Case#1: $n \geq 0$
Then it follows directly from theorem-6.4.1(division theorem) that there exist integers q and r s.t. n = mq + r where $0 \leq r < m$

Case#2: n < 0
Then -n is +ve. Hence we can choose some integers q and r s.t. $0 \leq r < m$ and
-n = qm + r
=> n = -qm - r
=> n = -qm - r + m - m
=> n = -(q+1)m + (m-r)

Let q' = -(q+1) and r' = (m-r). clearly q' and r' are integers and $0 \leq r' < m$

so, n = q'm + r'

(b) We will prove it by contradiction. Let us assume there exist distinct integers $q_1, q_2$ and distinct integers $r_1, r_2$ s.t. $0 \leq r_1,r_2 < m$ and
$n = q_1m + r_1$ and
$n = q_2m + r_2$

so, $q_1m + r_1 = q_2m + r_2$
=> $m = \frac{r_2 - r_1}{q_1 - q_2}$

Since $0 \leq r_1,r_2 < m$, so $|r_2 - r_1| < m$.
Also, $|q_1 - q_2| > 1$

Thus $\frac{|r_2 - r_1|}{|q_1 - q_2|} < m$. So m can not be equal to $\frac{r_2 - r_1}{q_1 - q_2}$. So we have a contradiction and hence distinct $q_1, q_2$ and distinct $r_1, r_2$ are not possible. So for every n and m, there exist only unique integers q and r s.t. n = qm + r

(c) Let us choose m = 2. Then For every integer n, we can choose integers q and r s.t. n = 2q + r and $0 \leq r < 2$. So only 2 following cases are possible

Case#1: r = 0
Then n = 2q. Then n is even

Case#2: r = 1
Then n = 2q + 1. Then n is odd

Since n is arbitrary, so every integer is either even or odd.


Ex-14: Let a be maximum of 5k and k(k+1). Let n be an arbitrary integer greater than a. Using result of ex-13(a) we can choose some integers q and r s.t. n = kq + r and $0 \leq r < k$.

Assume $q \leq 4$. Then $n = kq + r \leq 4k + r \leq 5k \leq a$. Since $n \leq a$ is not possible by assumption, hence $q \geq 5$. Then from example-6.1.3 it follows that $2^q \geq q^2$.

Now, assume $q \leq k$. Then $n = kq + r \leq k^2 + r \leq k^2 + k = k(k+1) \leq a$. Since $n \leq a$ is not possible by assumption, hence $q \geq (k+1)$.

So, $q \geq (k+1)$
=> $q^2 \geq q(k+1) = qk + q > qk + r = n$

Thus $q^2 \geq n$

Since $2^q \geq q^2$, so $2^q \geq n$. Then $2^{(kq+r)} \geq 2^r.n^k$. Then $2^{(kq+r)} \geq n^k$. Thus $2^n \geq n^k$.


Ex-15:
(a) Suppose, for every m s.t. $m \geq 1$ and m < k, $a_1f_1 + a_2f_2 + .. + a_mf_m \in O(g)$.

Now |f|
= |$a_1f_1 + a_2f_2 + .. + a_kf_k$|
= |$(a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}) + a_kf_k$|
$\leq |a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}| + |a_kf_k|$

Since $f_k \in O(g)$ so we can choose some $a \in Z^+$ and $c \in R^+$ s.t. for every n > a, $|f_k(n)| \leq c|g(n)|$

By induction hypothesis, $a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1} \in O(g)$, so we can choose some $a' \in Z^+$ and $c' \in R^+$ s.t. for every n > a',
$|a_1f_1(n) + a_2f_2(n) + .. + a_{k-1}f_{k-1}(n)| \leq c'|g(n)|$

Let a'' be maximum of a and a'. Then for every n > a''

|f(n)|
$\leq |a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}| + |a_kf_k|$
$\leq c'|g(n)| + c|a_k||g(n)| = (c' + c|a_k|)|g(n)|$

Thus, $f \in O(g)$

(b) Using result of ex-14, for every positive integer k we can choose some positive integer a s.t. for every n > a, $2^n \geq n^k$. Then all of $1, n, n^2, n^3, ....$ are elements of $O(2^n)$ or O(g). So using result of part(a), f is also element of O(g).

Ex-16:
(a) We can choose integers s and t s.t. d = as + bt.

Also by division theorem we can choose integers q and r s.t. a = dq + r and $0 \leq r < d$.

Then a = (as + bt)q + r
=> a = asq + btq + r
=> r = (1-sq)a + (-tq)b

Then $r \in S$. Since d is smallest element of S, so $d \leq r$. But r < d. Hence, the only value possible for r is 0. Thus a = dq and Hence d|a. By similar argument we can prove that d|b also.

(b) We can choose integers s and t s.t. d = as + bt. Since c|a and c|b, so c|(as) and c|(bt) both. Hence c|(as+bt) and so c|d.


Ex-17:
(a) Suppose p divides ab. Let d be the greatest common divisor of a and p then by ex-16 we can choose integers s and t s.t.
d = as + pt

Since d is gcd of a and p, so it divides p. Since p is prime, so d is either 1 or p. Let us consider both the cases.

Case#1: d = 1
Then 1 = as + pt. Since p|ab, so we can choose some real number k s.t. ab = kp. Then a = $\frac{kp}{b}$.
Then 1 = $s\frac{kp}{b} + pt$
=> b = skp + ptb
=> b = (sk + tb)p

Thus p divides b.

Case#2: d = p
Then p = as + pt
=> a = $\frac{p(1-t)}{s}$

Thus p divides a.

From above 2 cases its clear that either p|a or p|b.

(b) Let n be an arbitrary natural number s.t. $n \geq 1$. Suppose for every $1 \leq k < n$, if p divides $a_1a_2a_3...a_k$ then $p|a_i$ for some i, $1 \leq i \leq k$.

Suppose p divides $a_1a_2a_3...a_n$.
=> p divides $(a_1a_2a_3...a_{n-1}).a_n$

then, by using result of ex-17(a) either p divides $a_1a_2a_3...a_{n-1}$ or p divides $a_n$. Let us consider both the cases.

Case#1: p divides $a_1a_2a_3...a_{n-1}$
Then, by induction hypothesis, we can choose some i, $1 \leq i \leq (n-1)$ s.t. p divides $a_i$

Case#2: p divides $a_n$

Thus we can choose some i, $1 \leq i \leq n$ s.t. p divides $a_i$


Ex-18: We will use induction over j.

Base case: j = 1. Suppose $p_1, q_1, q_2, ..., q_k$ are all prime numbers s.t. $p_1 = q_1q_2...q_k$. Since $p_1$ is prime, so clearly k = 1 and $p_1 = q_1$

Induction Step: Suppose j be an arbitrary integer s.t. $j \geq 1$ and for all $k \geq 1$ and for all non decreasing sequence of primes $p_1,p_2,...,p_j$ and $q_1,q_2,...,q_k$ if $p_1p_2...p_j = q_1q_2...q_k$ then both the sequences are same.

Now suppose $p_1,p_2,...,p_j,p_{j+1}$ and $q_1,q_2,...,q_k$ are non-decreasing sequences of primes s.t.
$p_1p_2...p_jp_{j+1} = q_1q_2...q_k$

clearly $p_{j+1}$ divides $q_1q_2...q_k$, so by result of ex-17(b) we can choose some i s.t. $p_{j+1} = q_i$. Since $q_i \leq q_k$,
so $p_{j+1} \leq q_k$ ... (i)

Also, $q_k$ divides $p_1p_2...p_jp_{j+1}$, so by result of ex-17(b) we can choose some i s.t. $q_k = p_i \leq p_{j+1}$. Thus $q_k \leq p_{j+1}$... (ii)

From (i) and (ii), its clear that $p_{j+1} = q_k$.

Then $p_1p_2...p_j = q_1q_2...q_{k-1}$. By induction hypothesis both these sequences are same and hence the sequences $p_1,p_2,...,p_j,p_{j+1}$ and $q_1,q_2,...,q_k$ are same.


Ex-19: Scratchwork:
$a_0 = 1$
$a_1 = 1 + a_0 = 2$
$a_2 = 1 + a_0 + a_1 = 4$
$a_3 = 1 + a_0 + a_1 + a_2 = 8$
$a_4 = 1 + a_0 + a_1 + a_2 + a_3 = 16$

we can guess that $a_n = 2^n$

There is another way to find it. Let us look at that

$a_{n+1} = 1 + \sum_{i=0}^{n}a_i$
=> $a_{n+1} = 1 + \sum_{i=0}^{n-1}a_i + a_n$
=> $a_{n+1} = a_n + a_n$
=> $a_{n+1} = 2a_n$
=> $a_{n+1} = 2^2a_{n-1}$
=> $a_{n+1} = 2^3a_{n-2}$
=> $a_{n+1} = 2^4a_{n-3}$
...
...
=> $a_{n+1} = 2^{n+1}a_{n-n}$
=> $a_{n+1} = 2^{n+1}a_0$
=> $a_{n+1} = 2^{n+1}$

Formal Proof:

The formula is, for any natural number n, $a_n = 2^n$

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

Induction step: Suppose for arbitrary natural number n, $a_n = 2^n$

Now, $a_{n+1}$
= $1 + \sum_{i=0}^{n}a_i$
= $1 + \sum_{i=0}^{n-1}a_i + a_n$
= $a_n + a_n$
= $2a_n$
= $2.2^n$
= $2^{n+1}$


Ex-20: Scratchwork:
Let $F_n$ denotes nth fibonacci number.

$a_0 = 1 = \frac{F_2}{F_1}$
$a_1 = 1 + 1 = 2 = \frac{F_3}{F_2}$
$a_2 = 1 + \frac{1}{2} = \frac{3}{2} = \frac{F_4}{F_3}$
$a_3 = 1 + \frac{2}{3} = \frac{5}{3} = \frac{F_5}{F_4}$
$a_4 = 1 + \frac{3}{5} = \frac{8}{5} = \frac{F_6}{F_5}$
$a_5 = 1 + \frac{5}{8} = \frac{13}{8} = \frac{F_7}{F_6}$

easy enough to guess that $a_n = \frac{F_{n+2}}{F_{n+1}}$

Proof:

Suppose for every k < n, $a_k = \frac{F_{k+2}}{F_{k+1}}$

Now, $a_n$
= $1 + \frac{1}{a_{n-1}}$ (apply induction hypothesis to get)
= $1 + \frac{F_n}{F_{n+1}}$
= $\frac{F_{n+1} + F_n}{F_{n+1}}$
= $\frac{F_{n+2}}{F_{n+1}}$

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}(\frac{(n+1)^2}{n+2})$
= $\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(1)}{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}[\frac{(3n^2 - n - 2)(n+2) + 4(n+1)}{4(n+1)(n+2)}]$
= $\frac{1}{n}[\frac{3n^3 - n^2 - 2n + 6n^2 - 2n - 4 + 4n + 4}{4(n+1)(n+2)}]$
= $\frac{1}{n}[\frac{3n^3 + 5n^2}{4(n+1)(n+2)}]$
= $\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 = $(2(0) + 1)^2$ = 1
RHS = $\frac{(0+1)(2.0+1)(2.0+3)}{3}$ = $\frac{(1)(1)(3)}{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)]$
= $(2n+3)[\frac{(2n^2 + 3n + 1) + (6n+9)}{3}]$
= $(2n+3)[\frac{2n^2 + 9n + 10}{3}]$
= $(2n+3)[\frac{2n^2 + 4n + 5n + 10}{3}]$
= $(2n+3)[\frac{(n+2)(2n+5)}{3}]$
= $\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 $\leq$ RHS

Induction step:

Let, $\sum_{i=1}^{n} \frac{1}{i^2} \leq 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}$
$\leq (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}$
$\leq (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 = $ca_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 \geq m \rightarrow H_n - H_m \geq \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 \geq \frac{n-m}{n}$

Now, $H_{n+1} - H_m$
= $(\sum_{i=1}^{n+1} \frac{1}{i}) - 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}$
$\geq \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 $\geq$ m, so $\frac{n}{m} \geq 1$)
$\geq \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} \geq 1 + \frac{n}{2}$

Now, using part(a) $H_{2^{n+1}} - H_{2^n}$
$\geq \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} \geq \frac{1}{2}$
=> $H_{2^{n+1}} \geq H_{2^n} + \frac{1}{2}$
=> $H_{2^{n+1}} \geq 1 + \frac{n}{2} + \frac{1}{2}$
=> $H_{2^{n+1}} \geq 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 = nH_n - n$

Now, $\sum_{k=1}^{n} H_k$
= $(\sum_{k=1}^{n-1} H_k) + H_n$
= $nH_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} (i(i!))$ = (n+1)! - 1
Proof:

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

Induction step: Let $\sum_{i=1}^{n} (i(i!))$ = (n+1)! - 1

Now, $\sum_{i=1}^{n+1} (i(i!))$
= $\sum_{i=1}^{n} (i(i!))$ + (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{[(n+1)! - 1](n+2)}{(n+2)!} + \frac{(n+1)}{(n+2)!}$
= $\frac{1}{(n+2)!}[(n+2)! - (n+2) + (n+1)]$
= $\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 $\geq 1$, $2^n > n$

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

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

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

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

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

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

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

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

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

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


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

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

Now, $(k^2 + (n+1))! = (k^2 + n + 1).(k^2 + n)! \geq (k^2 + n + 1).k^{2n} = k^{2(n+1)} + (n+1).k^{2n} \geq 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)! \geq k^{2k^2}$
=> $(2k^2)! \geq k^{2k^2}$

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

Now, (n+1)! = (n+1).n! $\geq (n+1).k^n \geq 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, ${(a^m)}^0 = 1 = a^{m(0)}$

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

Now, ${(a^m)}^{(n+1)} = {(a^m)}^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 = {(a_{n-1})}^2 = {(a_{n-2})}^{2^2} = {(a_{n-3})}^{2^3} ... = {(a_{n-n})}^{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} = {(a_n)}^2 = {(2^{2^n})}^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(A)$ 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 \geq k$. For any set A, that has n elements, $P_k(A)$ 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(A) = P_k(B) \cup \{ X \cup \{x\} | X \in P_{k-1}(B) \}$

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

Then, # of elements in $P_k(A)$ = [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} [nCk]x^{n-k}y^k$

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

= $(x+y).(x+y)^n$
= $(x+y).\sum_{k=0}^{n} [nCk]x^{n-k}y^k$

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

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

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

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

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

= $\sum_{k=0}^{n+1} [(n+1)Ck]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[nCk] = {(-1)}^0[nC0] + {(-1)^1}[nC1] = 1 - 1 = 0$ = RHS

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

Now, $\sum_{k=0}^{n+1}{(-1)}^k[(n+1)Ck]$

= ${(-1)}^0[(n+1)C0] + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}[(n+1)C(n+1)]$

= ${(-1)}^0 + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k[(n+1)Ck] + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k([nCk] + [nC(k-1)]) + {(-1)}^{n+1}$

= $1 + \sum_{k=1}^{n}{(-1)}^k[nCk] + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $({(-1)}^0[nC0] + \sum_{k=1}^{n}{(-1)}^k[nCk]) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $(\sum_{k=0}^{n}{(-1)}^k[nCk]) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $(0) + \sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

= $\sum_{k=1}^{n}{(-1)}^k[nC(k-1)] + {(-1)}^{n+1}$

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

= $\sum_{l=0}^{n-1}{(-1)}^{l+1}[nCl] + {(-1)}^{n+1}$

= $\sum_{l=0}^{n-1}{(-1)}^{l+1}[nCl] + {(-1)}^{n+1}[nCn]$

= $\sum_{l=0}^{n}{(-1)}^{l+1}[nCl]$

= $-\sum_{l=0}^{n}{(-1)}^l[nCl]$

= 0


Ex-20: As given in the hint, we will prove that for all $n \geq 1$, $0 < a_n < \frac{1}{2}$

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

clearly, $0 < a_1 < \frac{1}{2}$

Induction step: Let n be arbitrary natural number greater than or equal to 1 and $0 < a_n < \frac{1}{2}$

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

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

Thus, $0 < a_{n+1} < \frac{1}{4}$

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' X A'$. Since $A' \subseteq A$, so $(x,x) \in R$ also. Since $(x,x) \in A' X A'$ 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' X A'$. 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 \{a\} X A$ 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 \{a\} X A$ and $(y,x) \in \{a\} X A$
Then x = y = a

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

Case#4: $(x,y) \in \{a\} X A$ 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 \{a\} X A$ and $(y,z) \in \{a\} X A$
Then x = y = a. Thus $(x,z) \in \{a\} X A$. Then $(x,z) \in T$

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

Case#4: $(x,y) \in \{a\} X A$ and $(y,z) \in T'$
Then x = a. Since $(a,z) \in \{a\} X A$, so $(x,z) \in \{a\} X A$. 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 \{a\} X A$ and hence $(x,y) \in T$

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

Case#3: $x \neq a$ and $y \neq 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 \{a\} X A$. 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 ((x,y) \in T' \lor (y,x) \in T')$.
Now let $A_1$ = {$x \in A | (x,b) \in T'$} , $A_2$ = $A \setminus A_1$ and T = $T' \cup (A_1 X A_2)$

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 \lor 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' ((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 ((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 \neq 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((b,y) \in R \circ R)$

(b) Let A = set of all the contestants
R = {$(x,y) \in A X A | x beats y$}

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

From part(a), since $A \subseteq A$, we can choose some $a \in A$ s.t. $\forall y \in A((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(2^{2^n}) - 2(2^{2^n}) - 2 + 2$
= $2^{2^{(n+1)}} + 1$
= $F_{n+1}$


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

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


Ex-7:
(a) $(a - b)^2 \geq 0$
=> $a^2 + b^2 - 2ab \geq 0$
=> $a^2 + b^2 \geq 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} \geq 2$

(b) $(c - a)(c - b) \geq 0$
=> $c^2 - cb - ca + ab \geq 0$
=> $ab + c^2 - cb \geq 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} \geq \frac{ca}{ca}$
=> $\frac{b}{c} + \frac{c}{a} - \frac{b}{a} \geq 1$

(c) Base case: For n = 2, $\frac{a_1}{a_2} + \frac{a_2}{a_1} \geq 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} \geq 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}$
$\geq 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} \geq 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} \geq n + 1$


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

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

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

Induction step: Let $\frac{a_1 + a_2 + a_3 + ... + a_{2^n}}{2^n} \geq (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}[(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 \geq n_0$ s.t.

$\frac{a_1 + a_2 + a_3 + ... + a_n}{n} < (a_1.a_2.a_3...a_n)^{\frac{1}{n}}$

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

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 \geq 1$ s.t. $2^n \geq 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
$\leq \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 = $\emptyset$, $P(A) = \{\emptyset\}$, 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(B)$ has $2^n$ elements.

Now $P(A)$ = $P(B) \cup \{ y \cup \{x\} | y \in P(B) \}$

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

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

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


Ex-11: Base case: A set with 2 elements, A = {a,b}, $P(A)$ = {{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(A)$ = $P(B) \cup $ {{x,y} | $y \in B$ }

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

So, # of elements in $P(A)$ = # of elements in $P(B)$ + # 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 N P(n)$:
First prove P(0), and then prove $\forall n \in N (P(n) \rightarrow P(n+1))$. 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 (P(n) \rightarrow P(n+1))$ 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 (P(n) \rightarrow P(n+1))$. 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 $\geq$ 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{(n(n+1)(2n+1)}{6}$

Now, $0^2 + 1^2 + 2^2 + ... + n^2 + (n+1)^2$
= $\frac{(n(n+1)(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{(n(n+1)}{2}]^2$

Now, $0^3 + 1^3 + 2^3 + ... + n^3 + (n+1)^3$
= $[\frac{(n(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 \geq 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 | 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 | [(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|(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(0) - 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(0) - 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(9k) - 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) + ab^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(0) + 1} + b^{2(0) + 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^2b^{2n+1} + b^{2n+3}$
= $a^2(a+b)k - b^{2n+1}(a^2 - b^2)$
= $(a+b)(a^2k - b^{2n+1}(a-b))$

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 \geq 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 (mod 3)$
Inductive step:
Let n be a arbitrary natural number s.t. $n \equiv 0 (mod 3)$ or $n \equiv 1 (mod 3)$ or $n \equiv 2 (mod 3)$. Let us consider all the possible cases for (n+1)

Case#1: $n \equiv 0 (mod 3)$
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 (mod 3)$

Case#2: $n \equiv 1 (mod 3)$
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 (mod 3)$

Case#3: $n \equiv 2 (mod 3)$
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 (mod 3)$

Thus $(n+1) \equiv 0 (mod 3)$ or $(n+1) \equiv 1 (mod 3)$ or $(n+1) \equiv 2 (mod 3)$


Ex-16: Base case: For n = 1. LHS = $2.2^1$ = 4, RHS = $(1)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 = n2^{n+1}$

Now, $2.2^1 + 3.2^2 + 4.2^3 + ... + (n+1)2^n + (n+2)2^{n+1}$
= $n2^{n+1} + (n+2)2^{n+1}$
= $n2^{n+1} + n2^{n+1} + 2^{n+2}$
= $n2^{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 + 2n3^{n+1}$
P(n) = $1 + n3^{n+1}$

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

Formal Proof:

Base case: For n = 0. LHS = $1.3^0$ = 1, RHS = $1 + (0)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 + n3^{n+1}$

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


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

Induction step:

Let n be an arbitrary natural number. if n is even then $a^n > 0$ or if n is odd then $a^n < 0$. 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 $a^{n+1} < 0$

Case#2: n is odd and $a^n < 0$
(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. $0 < a^n < b^n$.

clearly, $0 < a^{n+1}$.

Now, $b^{n+1} = bb^n > ba^n > aa^n = a^{n+1}$
Thus, $0 < a^{n+1} < b^{n+1}$

(b) TODO

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

Now $a^{n+1} + b^{n+1} - ab^n - ba^n$
= $a^{n+1} - ab^n + b^{n+1} - ba^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), $a^n < b^n$
=> $(b^n - a^n) > 0$

also (b-a) > 0

Hence $a^{n+1} + b^{n+1} - ab^n - ba^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
$ab + ba < a^2 + b^2$
=> $2ab < a^2 + b^2$

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. $(\frac{a+b}{2})^n < \frac{a^n + b^n}{2}$

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

$(\frac{a+b}{2})^{n+1} < \frac{a^n + b^n}{2}.\frac{a+b}{2}$
=> $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4}$

from part(c), $ab^n + ba^n < a^{n+1} + b^{n+1}$
so, $\frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4} < \frac{2(a^{n+1} + b^{n+1})}{4} = \frac{a^{n+1} + b^{n+1}}{2}$

Hence, $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1}}{2}$

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 $\lnot \exists a_1 \in A \exists a_2 \in A (f(a_1) = f(a_2) \land a_1 \neq 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 (f(a_1) = f(a_2) \rightarrow a_1 = a_2)$

Onto:
A function f:A -> B is called onto if $\forall b \in B \exists a \in A (f(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) ($\rightarrow$) Let (x,y) be an arbtirary element in $f \circ f$.
So, y =$(f \circ f)(x)$
= 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)(x)$ = 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) = {$y \in R | y^2 < 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)(a) = 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)(x)$ = g(f(x)) = g(u)
Also $(g \circ f)(y)$ = 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(b_1) = g(b_2)$ but $b_1 \neq b_2$. Since f is onto, so we can choose $a_1$ and $a_2$ in A s.t. $f(a_1) = b_1$ and $f(a_2) = b_2$ and $a_1 \neq a_2$. Thus $(g \circ f)(a_1)$ = $(g \circ f)(a_2)$ and $a_1 \neq 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)(a) = 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 \neq 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 \neq c$. Then there does not exist any $x \in A$ s.t. f(x) = c. Hence f is not onto.


Ex-12: ($\rightarrow$) 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)(a) = (f \cup g)(b) = 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)(x) = (f \cup g)(y) = 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) ($\rightarrow$) 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: ($\rightarrow$) 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 (f(x) = f(y) \rightarrow 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 (f(x) = f(y) \rightarrow x = y)$


Ex-17: Suppose f is onto, g:B -> C , h:B -> C and $g \circ f$ = $h \circ f$.
(a) ($\rightarrow$) 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 (g(x) = c_1)$, $\forall x \in B \setminus \{b\} (h(x) = c_1)$ and h(b) = $c_2$. Then $g \neq h$, so $g \circ f \neq h \circ f$ and therefore we can choose some $a \in A$ s.t. g(f(a)) $\neq$ h(f(a)). But by definition of g and h, there is only one $x \in B$ s.t. g(x) $\neq$ 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$.
($\rightarrow$) 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 (g(x) = b_1)$ and $\forall x \in A (h(x) = b_2)$.
Now for every $x \in A$, $(f \circ g)(x)$ = f(g(x)) = f($b_1$) = f($b_2$) = f(h(x)) = $(f \circ h)(x)$. 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)(x)$ = 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)(x)$
=> $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)(x)$ = $i_R(f(x))$ = 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)(x)$ = $j_1(g(x))$ = $j_1(j_2(h(x)))$ = $(j_1 \circ j_2)(h(x))$. Let j = $j_1 \circ j_2$. Then $(j_1 \circ g)(x)$ = $(j \circ h)(x)$. 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)(x)$ = f($i_R(x)$) = 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$.
($\rightarrow$) Suppose $i_RRf$. 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(x)$ = $(j \circ f)(x)$ = j(f(x)) = j(f(y)) = $(j \circ f)(y)$ = $i_R(y)$ = 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 ((R \setminus A) X \{0\})$.
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 \setminus A$. Then $(x,0) \in ((R \setminus A) X \{0\})$. 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)(x)$ = h(f(x)) = x = $i_R(x)$. Since x is arbitrary, so $i_R = h \circ f$

Hence $i_RRf$

(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.

($\rightarrow$) Suppose $\forall f \in F (fRg)$. 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)(x)$ = 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)(x)$ = 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_RRg$. 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) $fRi_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)(x)$
= h(g(x))
= $(j_2 \circ j_1)(g(x))$
= $j_2(j_1(g(x)))$
= $j_2((j_1 \circ g)(x))$
= $j_2(i_R(x))$
= $(j_2 \circ i_R)(x)$
= f(x)

Thus f = $h \circ g$. Hence fRg. And, so $[f]_S T [g]_S$. Since f is arbitrary so $\forall f \in F ([f]_S T [g]_S)$, 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 $[g]_S T [f]_S$. Hence set of all constant functions is smallest element of $F/S$