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}}$
Subscribe to:
Post Comments (Atom)
So finish the book already :-P plenty more books where this came from :-P
ReplyDelete@Ravi... trust me, I'm more eager to finish it and start the next one than you are :).
ReplyDelete