Issues faced with Mule-2.2.1

Mule is one of the open-source(commercial support available) ESB. These are some of the showstoppers I faced while I used mule in one of my projects. (Things may get resolved in future versions though).

1. It does not support multiple headers. So, what it means is that, If you're doing some kind of login and your server sends multiple Set-Cookie header to mule in response then mule will ignore all but last Set-Cookie header. To add to the trouble, you'll read RFC-2109 and believe that concatenating all the cookies(using comma as separator) inside single Set-Cookie header will resolve it but it'll not as browsers don't honor the spec in this regard.



2. You can't set virtual host/port on a http request made from mule. So, if you want to use mule as a proxy to transparently pass the host header to the end server, well it will not.



3. Do not use MuleMessage.getPayloadAsString() in case your payload is Input-Stream, as it will read the whole stream ignoring Content-Length "property" completely and that will result in issues if your response was a http message with large binary content. Content-Length might also get messed up in the end response.



4. It is completely unintuitive, you will end up writing too much code inside xml configuration.

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

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

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\left(x\right)\in C$. Since C is arbitrary, so $\forall C\in Ff\left(x\right)\in F$ and hence $f\left(x\right)\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\left(x\right)\in B_{n+1}$. Then $f\left(x\right)\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\left(x\right)\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\ne \varnothing$
$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\ne \varnothing$

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\left(x\right)\in C$. Since C is arbitrary, so $\forall C\in Hf\left(x\right)\in H$ and hence $f\left(x\right)\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=\varnothing$ 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) $\le$ (m+n) = d(a,b) + d(b,c)

(b) TODO


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

Base case: n = 1
($\to$) 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 $\left(f\right(0),f(1\left)\right)\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}

($\to$) 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\backslash${(n+1,b)} is an R-path from a to c of length n. So, by induction hypothesis, $(a,c)\in R^n$. Also, $\left(f\right(n),f(n+1\left)\right)\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$

($\to$) 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\backslash i_A$. Then $(a,b)\in R$ and $a\ne 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\backslash 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}\backslash i_A$. Then $(a,b)\in R^{n+1}$ and $a\ne 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\le n$.
Now let us define g = f $\cup$ {(m+1,b)}. Consider following cases..

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

case#2: $b\in Ran\left(f\right)$
Then we can choose some $k\le 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\le 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$

($\to$) Let (a,b) be arbitrary element of $S\backslash i_A$. Then $(a,b)\in S$ and $a\ne 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\left(0\right)\ne f\left(n\right)$ and hence $a\ne 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\backslash 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\ne b$, so $(a,b)\notin i_A$. Then $(a,b)\in R^n\backslash 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)\ge n$. Then $i\ge j$.

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

Since $i\ge j$ and $j\ge i$, so $i=j$. Since i and j are arbitrary positive integers smaller than n, so


Ex-13: Let $f:j_n\to 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\le m$. Then $n\le (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

So, $\cup \{R^n\mid n>m\}\subseteq \cup \{R^n\mid 1\le n\le m\}$

Then S = $\cup \{R^n\mid n>1\}$ = $\cup \{R^n\mid 1\le n\le 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\le i\le 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\le i\le 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 NP\left(n\right)$.

To Prove a goal of the form $\forall n\in NP\left(n\right)$
Prove that , 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 . Then plugging n = 0, we get . Now, 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=n{3}^{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=k{3}^{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\left)3^{n-1}\right)+(2n+1)3^n$
= $(n-1)3^n+(2n+1)3^n$
= $3n.3^n$
= $n{3}^{n+1}$

Hence, by the assumptions of strong induction, $1.3^0+3.3^1+5.3^2+..+(2n+1)3^n=n{3}^{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:

Q(n) =

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

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

(b) Base case: For n = 0, Q(0) = , 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 . Then it follows from the givens that P(n). Thus . So Q(n+1).


Ex-2 Let q be arbitrary natural number. Suppose, for all k < q, $\neg \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 . Since q is arbitrary, so $\sqrt{2}$ is irrational.


Ex-3
(a) Assume $\sqrt{6}$ is rational. Let S = { $q\in Z+\mid \exists p\in Z+(\frac{p}{q}=\sqrt{6})$ }. Then $S\ne \varnothing$. 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 . 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\ge 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\ge 15$
Then $(n-3)\ge 12$ and . 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\ge 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\ge 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$
= $\left(\sum _{i=0}^{n-1}{F}_i\right)+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{\left(F_i\right)}^2=F_k{F}_{k+1}$

Now, $\sum _{i=0}^n{\left(F_i\right)}^2$
= $\left(\sum _{i=0}^{n-1}{\left(F_i\right)}^2\right)+{\left(F_n\right)}^2$ (apply induction hypothesis to get...)
= $F_{n-1}{F}_n+{\left(F_n\right)}^2$
= $F_n(F_{n-1}+F_n)$
= $F_n{F}_{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}$
= $\left(\sum _{i=0}^{n-1}{F}_{2i+1}\right)+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_m{F}_{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_m{F}_{0+1}$ = $0+F_m{F}_1$ = $F_m$
clearly LHS = RHS

Case#2: n = 1
Then LHS = $F_{m+1}$
RHS = $F_{m-1}{F}_1+F_m{F}_2$ = $F_{m-1}+F_m$ = $F_{m+1}$
clearly LHS = RHS

Case#3: $n\ge 2$
$F_{m+n}$
= $F_{m+n-1}+F_{m+n-2}$ (apply induction hypothesis to get...)
= $(F_{m-1}{F}_{n-1}+F_m{F}_n)+(F_{m-1}{F}_{n-2}+F_m{F}_{n-1})$
= $F_{m-1}(F_{n-1}+F_{n-2})+F_m(F_n+F_{n-1})$
= $F_{m-1}{F}_n+F_m{F}_{n+1}$

clearly, by strong induction, $F_{m+n}=F_{m-1}{F}_n+F_m{F}_{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\ge 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, ${\left(F_k\right)}^2+{\left(F_{k+1}\right)}^2=F_{2k+1}$

Let us consider following cases.

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

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

Case#3: n > 3
${\left(F_n\right)}^2+{\left(F_{n+1}\right)}^2$
= ${(F_{n-1}+F_{n-2})}^2+{(F_n+F_{n-1})}^2$
= ${\left(F_{n-1}\right)}^2+{\left(F_{n-2}\right)}^2+2F_{n-1}{F}_{n-2}+{\left(F_n\right)}^2+{\left(F_{n-1}\right)}^2+2F_n{F}_{n-1}$
= $({\left(F_{n-1}\right)}^2+{\left(F_{n-2}\right)}^2)+({\left(F_n\right)}^2+{\left(F_{n-1}\right)}^2)+2(F_{n-1}{F}_{n-2}+F_n{F}_{n-1})$

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

= $({\left(F_{n-1}\right)}^2+{\left(F_{n-2}\right)}^2)+({\left(F_n\right)}^2+{\left(F_{n-1}\right)}^2)+2F_{2n-2}$ (apply induction hypothesis to get)
= $\left(F_{2n-3}\right)+\left(F_{2n-1}\right)+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, ${\left(F_n\right)}^2+{\left(F_{n+1}\right)}^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\mid 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\mid 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_m{F}_{(k-1)m+1}$

by induction hypothesis, $F_m\mid F_{(k-1)m}$. Hence $F_m\mid \left(F_{m-1}{F}_{(k-1)m}\right)$. Also, $F_m\mid \left(F_m{F}_{(k-1)m+1}\right)$

So $F_m\mid 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}\left(\genfrac{}{}{0ex}{}{2k-i-2}{i}\right)$ and
$F_{2k}=\sum _{i=0}^{k-1}\left(\genfrac{}{}{0ex}{}{2k-i-1}{i}\right)$

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}\left(\genfrac{}{}{0ex}{}{2(n-1)-i-1}{i}\right)+\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{2(n-1)-i-2}{i}\right)$
= $\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i}\right)+\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-4}{i}\right)$

Let us look consider the 2nd term..
$\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-4}{i}\right)$ (let i = j-1)
= $\sum _{j=1}^{n-1}\left(\genfrac{}{}{0ex}{}{2n-j-3}{j-1}\right)$ (let j = i)
= $\sum _{i=1}^{n-1}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i-1}\right)$

So, $F_{2n-1}$
= $\sum _{i=0}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i}\right)+\sum _{i=1}^{n-1}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i-1}\right)$
= $(\left(\genfrac{}{}{0ex}{}{2n-3}{0}\right)+\sum _{i=1}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i}\right))+(\sum _{i=1}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-3}{i-1}\right)+\left(\genfrac{}{}{0ex}{}{n-2}{n-2}\right))$
= $1+\sum _{i=1}^{n-2}(\left(\genfrac{}{}{0ex}{}{2n-i-3}{i}\right)+\left(\genfrac{}{}{0ex}{}{2n-i-3}{i-1}\right))+1$
= $1+\sum _{i=1}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-2}{i}\right)+1$
= $\left(\genfrac{}{}{0ex}{}{2n-0-2}{0}\right)+\sum _{i=1}^{n-2}\left(\genfrac{}{}{0ex}{}{2n-i-2}{i}\right)+\left(\genfrac{}{}{0ex}{}{2n-(n-1)-2}{n-1}\right)$
= $\sum _{i=0}^{n-1}\left(\genfrac{}{}{0ex}{}{2n-i-2}{i}\right)$

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


Ex-8:
(a) ($\to$) 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{\left(\frac{1+\sqrt{5}}{2}\right)}^{n-1}+t{\left(\frac{1-\sqrt{5}}{2}\right)}^{n-1}+s{\left(\frac{1+\sqrt{5}}{2}\right)}^{n-2}+t{\left(\frac{1-\sqrt{5}}{2}\right)}^{n-2}$
= $s{\left(\frac{1+\sqrt{5}}{2}\right)}^{n-2}(\frac{1+\sqrt{5}}{2}+1)+t{\left(\frac{1-\sqrt{5}}{2}\right)}^{n-2}(\frac{1-\sqrt{5}}{2}+1)$
= $s{\left(\frac{1+\sqrt{5}}{2}\right)}^{n-2}\left(\frac{3+\sqrt{5}}{2}\right)+t{\left(\frac{1-\sqrt{5}}{2}\right)}^{n-2}\left(\frac{3-\sqrt{5}}{2}\right)$
= $s{\left(\frac{1+\sqrt{5}}{2}\right)}^{n-2}{\left(\frac{1+\sqrt{5}}{2}\right)}^2+t{\left(\frac{1-\sqrt{5}}{2}\right)}^{n-2}{\left(\frac{1-\sqrt{5}}{2}\right)}^2$
= $s{\left(\frac{1+\sqrt{5}}{2}\right)}^n+t{\left(\frac{1-\sqrt{5}}{2}\right)}^n$
= $a_n$

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

$a_1=s\left(\frac{1+\sqrt{5}}{2}\right)+t\left(\frac{1-\sqrt{5}}{2}\right)$
=> $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{\left(\frac{1+\sqrt{5}}{2}\right)}^n+t{\left(\frac{1-\sqrt{5}}{2}\right)}^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{\left(\frac{1+\sqrt{5}}{2}\right)}^n+t{\left(\frac{1-\sqrt{5}}{2}\right)}^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\ge 2$, $L_n={\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\left(\frac{1-\sqrt{5}}{2}\right)}^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=s{2}^n+t{3}^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$ = {$\varnothing$,{1}} , size = 2
$P_2$ = {$\varnothing$,{1},{2}}, size = 3
$P_3$ = {$\varnothing$,{1},{2},{3},{1,3}}, size = 5
$P_4$ = {$\varnothing$,{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 \left\{n\right\}\mid 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 \left\{n\right\}\mid 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\ge 1$, # of elements in $P_n$ = $F_{n+2}$


Ex-13:
(a) Let us consider both the possible cases:
Case#1: $n\ge 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

Case#2: n < 0
Then -n is +ve. Hence we can choose some integers q and r s.t. 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

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. and
$n=q_{1}m+r_1$ and
$n=q_{2}m+r_2$

so, $q_{1}m+r_1=q_{2}m+r_2$
=> $m=\frac{r_2-r_1}{q_1-q_2}$

Since , so .
Also, $\mid q_1-q_2\mid >1$

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

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

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

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

Thus $q^2\ge n$

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


Ex-15:
(a) Suppose, for every m s.t. $m\ge 1$ and m < k, $a_1{f}_1+a_2{f}_2+..+a_m{f}_m\in O\left(g\right)$.

Now |f|
= |$a_1{f}_1+a_2{f}_2+..+a_k{f}_k$|
= |$(a_1{f}_1+a_2{f}_2+..+a_{k-1}{f}_{k-1})+a_k{f}_k$|
$\le \mid a_1{f}_1+a_2{f}_2+..+a_{k-1}{f}_{k-1}\mid +\mid a_k{f}_k\mid$

Since $f_k\in O\left(g\right)$ so we can choose some $a\in Z^{+}$ and $c\in R^{+}$ s.t. for every n > a, $\mid f_k\left(n\right)\mid \le c\mid g\left(n\right)\mid$

By induction hypothesis, $a_1{f}_1+a_2{f}_2+..+a_{k-1}{f}_{k-1}\in O\left(g\right)$, so we can choose some $aʹ\in Z^{+}$ and $cʹ\in R^{+}$ s.t. for every n > a',
$\mid a_1{f}_1\left(n\right)+a_2{f}_2\left(n\right)+..+a_{k-1}{f}_{k-1}\left(n\right)\mid \le cʹ\mid g\left(n\right)\mid$

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

|f(n)|
$\le \mid a_1{f}_1+a_2{f}_2+..+a_{k-1}{f}_{k-1}\mid +\mid a_k{f}_k\mid$
$\le cʹ\mid g\left(n\right)\mid +c\mid a_k\mid \mid g\left(n\right)\mid =(cʹ+c\mid a_k\mid )\mid g\left(n\right)\mid$

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

(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\ge n^k$. Then all of $1,n,n^2,n^3,....$ are elements of $O\left(2^n\right)$ 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 .

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\le 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\ge 1$. Suppose for every , if p divides $a_1{a}_2{a}_3...a_k$ then $p\mid a_i$ for some i, $1\le i\le k$.

Suppose p divides $a_1{a}_2{a}_3...a_n$.
=> p divides $(a_1{a}_2{a}_3...a_{n-1}).a_n$

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

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

Case#2: p divides $a_n$

Thus we can choose some i, $1\le i\le 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_1{q}_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\ge 1$ and for all $k\ge 1$ and for all non decreasing sequence of primes $p_1,p_2,...,p_j$ and $q_1,q_2,...,q_k$ if $p_1{p}_2...p_j=q_1{q}_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_1{p}_2...p_j{p}_{j+1}=q_1{q}_2...q_k$

clearly $p_{j+1}$ divides $q_1{q}_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\le q_k$,
so $p_{j+1}\le q_k$ ... (i)

Also, $q_k$ divides $p_1{p}_2...p_j{p}_{j+1}$, so by result of ex-17(b) we can choose some i s.t. $q_k=p_i\le p_{j+1}$. Thus $q_k\le p_{j+1}$... (ii)

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

Then $p_1{p}_2...p_j=q_1{q}_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^2{a}_{n-1}$
=> $a_{n+1}=2^3{a}_{n-2}$
=> $a_{n+1}=2^4{a}_{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}}$