=================================================================================================
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.
No comments:
Post a Comment