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 \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}$

my emacs cheat-sheet

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

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

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

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

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


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

Mark:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cancel:
C-g

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

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

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

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

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

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

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

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

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

Ex-1:
(a) First, we prove that R' is reflexive in A'
Let x be arbitrary element of A'. Then $(x,x) \in A' 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}$