Definition 1: Base of the Canonical Extension : $\beta_0$
If a sequence of integers $C$ does not possess the property of normality (see Definition 1, here), then there exists $c,c'$ in the interval $(0,n)$ such that $c\notin C,c'\notin C$, $c + c' - n = a + b$ where $C = A+B$ and $a\in A$ and $b\in B$
Let $\beta_0\in B$ be the least number $b$ for which $c + c' - n = a + b$
Definition 2: Canonical Extension of the set $C$ : $C_1$
The equation $c + c' - n = a + \beta_0$ has a solution in the numbers $c$, $c'$, $a$ where $c\notin C$, $c'\notin C$; $a\in A$; $c$, $c'$, $a \in (0,n)$.
Let $C^{*}$ be the set of all numbers $c,c'$ included in the above solution so that $C\cap C^{*}$ is the empty set.
We will call $C_1 = C \cup C^{*}$ the "canonical extension" of the set $C$.
Definition 3: Canonical Extension of the set $B$ : $B_1$
Let $B^{*}$ be the set of all values $\beta_0 + n - c$ where $c\in C^{*}$
Each number $b*\in B^{*}$ can be written in the form $c' - a$ where $c' \in C^{*}$ and $a \in A$ [Since $\beta_0+n- c = c' - a$ from the equation $c + c' - n = a + \beta_0$ above]
Since $b*$ has the form $\beta_0+n-c$, it follows that $b* \ge \beta_0 \ge 0$
Since $b* = c' - a$, $b* \le c' \le n$
So, all numbers $b*\in B^{*}$ lie in the interval $(0,n)$.
For all numbers $b*\in B^{*}$, $b*\notin B$ since otherwise, $b* = c' - a$ would imply that since $c' = b* + a$, $c' \in C$ which is false.
We will call $B_1 = B\cup B^{*}$ the "canonical extension" of the set $B$.
Lemma 1: $A + B_1 = C_1$
Proof:
(1) Either $b_1\in B$ or $b_1\in B^{*}$
(2) If $b_1 \in B$, then $a + b_1 \in C \subseteq C_1$
(3) If $b_1 \in B^{*}$, then $b_1 = \beta_0 + n - c'$ where $c' \notin C$
(4) Since $c + c' - n = a + \beta_0$, $b_1 = c - a$
QED
Saturday, December 14, 2013
Wednesday, November 27, 2013
1.2 Mann's Theorem: Theorem 1.2.1. (H. B. Mann)
The details in these notes are taken from A. O. Gelfond & Yu. V. Linnik, elementary methods in analytic number theory, 1965 (translated by Amiel Fienstein/Revised and edited by L. J. Mordell).
Lemma 1. If $d(A) + d(B) > 1$, we can assume that $\exists A',B'$ such that:
(1) Assume that $d(A) + d(B) > 1$
(2) There exists $A',B'$ where $A' \subseteq A$ and $B' \subseteq B$ and $d(A')+d(B') \le 1$
(3) In fact, we can assume $d(A') + d(B')$ is as close to $1$ as we want since:
(a) We can assume that $d(B) \le d(A) < 1$.
Note: If $d(A)=1$, then we set $B' = B - \{1\}$ to get $d(A)+d(B')=1$
(c) We can assume that $1 - d(A) > \epsilon$
Note: If not, then we set $B' = B - \{1\}$ to get $\epsilon > 1 - d(A)-d(B')$
(d) There exists integers $x,y$ such that $1 - d(A) - \epsilon \le \frac{x}{y} < 1 - d(A)$
(e) From the definition of density, we know that $d(B) \le \frac{B(y)}{y}$
(f) Using $y$, we can build $B'$ by removing $B(y)-x$ elements from $B$.
Note 1: $\frac{x}{y} < d(B) \le \frac{B(y)}{y}$ since $d(A) + d(B) > 1$ but $d(A) + \frac{x}{y} < 1$.
Note 2: If for any reason the approach in step 3f doesn't work, we can choose a larger $x'$ so that $x' > x$ and $\frac{x'}{y'} = \frac{x}{y}$
QED
Lemma 2. if for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$, then $d(C) \ge d(A) + d(B)$.
Proof:
(1) Assume that for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$.
(2) Then, for any $n$, we have:
$$C(n) - C(n-m) \ge (d(A) + d(B))m$$
$$C(n-m)-C(n-m-m') \ge (d(A) + d(B))m'$$
$$C(n-m-m')-C(n-m-m-m'') \ge (d(A) + d(B))m''$$
$$\vdots$$
(3) Adding all of these values up, gets us to:
$$C(n) \ge (d(A)+d(B))(m + m' + m'' + \cdots) = (d(A) + d(B))n$$
(4) Divide both sides by $n$ to get:
$$\frac{C(n)}{n} \ge d(A)+d(B)$$
(5) Since this is true for all $n$, using the definition of infimum [see Definition 3, here], it follows that:
$$\inf_n{\frac{C(n)}{n}} \ge d(A)+d(B)$$
(6) This gets us to: $d(C) \ge d(A) + d(B)$. [see Definition 4, here]
QED
Lemma 3. If $A(n) + B(n) > n-1$, then $n$ occurs in $A+B$
Proof:
(1) Assume $A(n) + B(n) > n-1$
(2) Assume $n \notin C = A+B$ [If it is, we are already done.]
(3) Then: $A(n-1) = A(n)$ and $B(n-1) = B(n)$ so that:
$$A(n-1)+B(n-1)>n-1$$
(4) Let $a_1,a_2,\cdots,a_r$ and $b_1,b_2\cdots,b_s$ be the numbers of $[1,n-1]$ which appear in $A$ and $B$ respectively.
(5) So that, $r = A(n-1)$ and $s = B(n-1)$
(6) Then, the numbers $a_1, a_2, \cdots, a_r$ and $n - b_1, n_b2, \cdots, n - b_s$ are all distinct and belong to $[1,n-1]$
(7) But by assumption, there are more than $n-1$ of them which is impossible.
(8) Therefore, we reject our assumption in step #2.
QED
Definition 1: normal
A system of numbers $H \subset [0,n]$ is normal if for all $f \in [1,n]$; $f' \in [1,n]$; $f \notin H$; $f'\notin H$:
$$f + f' - n \notin H$$
Lemma 4. If $C$ is normal, then for every $n \ge 1$ one can find $m \in [1,n]$ such that:
$$C(n) - C(n-m) \ge (\alpha + \beta)m$$
where:
(1) We can assume that $n \notin C$
Note: if $n \in C$, then there is a trivial solution for $m=1$ since:
$$C(n)-C(n-m) = C(n)-C(n-1) = 1 \ge (d(A)+d(B))1$$
(2) Let $m$ be the least positive integer not belonging to $C$
(3) It is clear that $m \le n$
(4) We can assume that $m < n$ since:
(a) Assume that $m = n$
(b) $C(n) - C(n-m) = C(n) - C(0) = n-1$
(c) From Lemma 3 above, $A(n) + B(n) \le n-1$
(d) So, it follows that $C(n) - C(0) \ge A(n) + B(n) \ge (d(A) + d(B))n$
(5) Let $s \in [n-m,n]$ such that $0 < s+m-n < m$
(6) Now $s \in C$. If not, then we would have $s \notin C; m \notin C$ and $s+m-n \notin C$ but $s+m-n < m$ which goes against $m$ being the least positive integer not belonging to $C$.
(7) So, from step #5 and step #6, it follows that $C(n) - C(n-m) = m-1$
(8) Using Lemma 3 above, since $m \notin C$, it follows that $A(m) + B(m) \le m-1$.
(9) So, that, we have $C(n) - C(n-m) \ge A(m) + B(m) \ge (d(A) + d(B))m$
QED
Theorem 1.2.1 (H. B. Mann)
$$d(A+B) \ge \min(d(A) + d(B),1)$$
Lemma 1. If $d(A) + d(B) > 1$, we can assume that $\exists A',B'$ such that:
- $d(A') + d(B') = 1$
- $A' \subseteq A$
- $B' \subseteq B$
(1) Assume that $d(A) + d(B) > 1$
(2) There exists $A',B'$ where $A' \subseteq A$ and $B' \subseteq B$ and $d(A')+d(B') \le 1$
(3) In fact, we can assume $d(A') + d(B')$ is as close to $1$ as we want since:
(a) We can assume that $d(B) \le d(A) < 1$.
Note: If $d(A)=1$, then we set $B' = B - \{1\}$ to get $d(A)+d(B')=1$
(c) We can assume that $1 - d(A) > \epsilon$
Note: If not, then we set $B' = B - \{1\}$ to get $\epsilon > 1 - d(A)-d(B')$
(d) There exists integers $x,y$ such that $1 - d(A) - \epsilon \le \frac{x}{y} < 1 - d(A)$
(e) From the definition of density, we know that $d(B) \le \frac{B(y)}{y}$
(f) Using $y$, we can build $B'$ by removing $B(y)-x$ elements from $B$.
Note 1: $\frac{x}{y} < d(B) \le \frac{B(y)}{y}$ since $d(A) + d(B) > 1$ but $d(A) + \frac{x}{y} < 1$.
Note 2: If for any reason the approach in step 3f doesn't work, we can choose a larger $x'$ so that $x' > x$ and $\frac{x'}{y'} = \frac{x}{y}$
QED
Lemma 2. if for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$, then $d(C) \ge d(A) + d(B)$.
Proof:
(1) Assume that for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$.
(2) Then, for any $n$, we have:
$$C(n) - C(n-m) \ge (d(A) + d(B))m$$
$$C(n-m)-C(n-m-m') \ge (d(A) + d(B))m'$$
$$C(n-m-m')-C(n-m-m-m'') \ge (d(A) + d(B))m''$$
$$\vdots$$
(3) Adding all of these values up, gets us to:
$$C(n) \ge (d(A)+d(B))(m + m' + m'' + \cdots) = (d(A) + d(B))n$$
(4) Divide both sides by $n$ to get:
$$\frac{C(n)}{n} \ge d(A)+d(B)$$
(5) Since this is true for all $n$, using the definition of infimum [see Definition 3, here], it follows that:
$$\inf_n{\frac{C(n)}{n}} \ge d(A)+d(B)$$
(6) This gets us to: $d(C) \ge d(A) + d(B)$. [see Definition 4, here]
QED
Lemma 3. If $A(n) + B(n) > n-1$, then $n$ occurs in $A+B$
Proof:
(1) Assume $A(n) + B(n) > n-1$
(2) Assume $n \notin C = A+B$ [If it is, we are already done.]
(3) Then: $A(n-1) = A(n)$ and $B(n-1) = B(n)$ so that:
$$A(n-1)+B(n-1)>n-1$$
(4) Let $a_1,a_2,\cdots,a_r$ and $b_1,b_2\cdots,b_s$ be the numbers of $[1,n-1]$ which appear in $A$ and $B$ respectively.
(5) So that, $r = A(n-1)$ and $s = B(n-1)$
(6) Then, the numbers $a_1, a_2, \cdots, a_r$ and $n - b_1, n_b2, \cdots, n - b_s$ are all distinct and belong to $[1,n-1]$
(7) But by assumption, there are more than $n-1$ of them which is impossible.
(8) Therefore, we reject our assumption in step #2.
QED
Definition 1: normal
A system of numbers $H \subset [0,n]$ is normal if for all $f \in [1,n]$; $f' \in [1,n]$; $f \notin H$; $f'\notin H$:
$$f + f' - n \notin H$$
Lemma 4. If $C$ is normal, then for every $n \ge 1$ one can find $m \in [1,n]$ such that:
$$C(n) - C(n-m) \ge (\alpha + \beta)m$$
where:
- $C=A+B$
- $\alpha = d(A)$
- $\beta = d(B)$
(1) We can assume that $n \notin C$
Note: if $n \in C$, then there is a trivial solution for $m=1$ since:
$$C(n)-C(n-m) = C(n)-C(n-1) = 1 \ge (d(A)+d(B))1$$
(2) Let $m$ be the least positive integer not belonging to $C$
(3) It is clear that $m \le n$
(4) We can assume that $m < n$ since:
(a) Assume that $m = n$
(b) $C(n) - C(n-m) = C(n) - C(0) = n-1$
(c) From Lemma 3 above, $A(n) + B(n) \le n-1$
(d) So, it follows that $C(n) - C(0) \ge A(n) + B(n) \ge (d(A) + d(B))n$
(5) Let $s \in [n-m,n]$ such that $0 < s+m-n < m$
(6) Now $s \in C$. If not, then we would have $s \notin C; m \notin C$ and $s+m-n \notin C$ but $s+m-n < m$ which goes against $m$ being the least positive integer not belonging to $C$.
(7) So, from step #5 and step #6, it follows that $C(n) - C(n-m) = m-1$
(8) Using Lemma 3 above, since $m \notin C$, it follows that $A(m) + B(m) \le m-1$.
(9) So, that, we have $C(n) - C(n-m) \ge A(m) + B(m) \ge (d(A) + d(B))m$
QED
Theorem 1.2.1 (H. B. Mann)
$$d(A+B) \ge \min(d(A) + d(B),1)$$
1.1 Additive Properties of Sequences - Theorem 1.1.2 (L. G. Shnirelman)
The details in these notes are taken from A. O. Gelfond & Yu. V. Linnik, elementary methods in analytic number theory, 1965 (translated by Amiel Fienstein/Revised and edited by L. J. Mordell).
Definition 5: Additive Basis
A subset $A \subseteq \mathbb{N}$ with the property that $A + A + \cdots + A = \mathbb{N}$ for a finite sum.
Theorem 1.1.2 (L. G. Shnirelman) Every sequence with a positive density is a basis for the natural numbers.
Proof:
(1) Let $A^{(k)} = \underbrace{A + A + \dots + A}_{k\,\text{times}}$
(2) Using the Corollary from Theorem 1.1.1, we have:
$$d(A^{(k)}) \ge 1 - (1 - d(A))^k$$
(3) For sufficiently large $k$, we have:
$$d(A^{(k)})>\frac{1}{2}$$
since $0 \le\frac{A(n)}{n}\le 1$ and $d(A)=\inf\limits_{n}\frac{A(N)}{n}$.
(4) For this $k$, the number of terms of $A^{(k)}$ in the interval $[1,n]$ will be greater than $\frac{n}{2}$.
(5) If $a_i$ ranges over the terms of $A^{(k)}$ which do not exceed $n$, then there exists $i_1,i_2$ such that: $a_{i_1} = n - a_{i_2}$.
Note: If $i_1,i_2$ don't exist, then there are more than $2*(\frac{n}{2}+1)=n+2$ values in $[0,n]$ which is impossible.
(6) So, there exists $k$ such that for any $n$, there exists $a_{i_1}, a_{i_2} \in A^{(k)}$ such that $n = a_{i_1} + a_{i_2}$.
QED
Definition 5: Additive Basis
A subset $A \subseteq \mathbb{N}$ with the property that $A + A + \cdots + A = \mathbb{N}$ for a finite sum.
Theorem 1.1.2 (L. G. Shnirelman) Every sequence with a positive density is a basis for the natural numbers.
Proof:
(1) Let $A^{(k)} = \underbrace{A + A + \dots + A}_{k\,\text{times}}$
(2) Using the Corollary from Theorem 1.1.1, we have:
$$d(A^{(k)}) \ge 1 - (1 - d(A))^k$$
(3) For sufficiently large $k$, we have:
$$d(A^{(k)})>\frac{1}{2}$$
since $0 \le\frac{A(n)}{n}\le 1$ and $d(A)=\inf\limits_{n}\frac{A(N)}{n}$.
(4) For this $k$, the number of terms of $A^{(k)}$ in the interval $[1,n]$ will be greater than $\frac{n}{2}$.
(5) If $a_i$ ranges over the terms of $A^{(k)}$ which do not exceed $n$, then there exists $i_1,i_2$ such that: $a_{i_1} = n - a_{i_2}$.
Note: If $i_1,i_2$ don't exist, then there are more than $2*(\frac{n}{2}+1)=n+2$ values in $[0,n]$ which is impossible.
(6) So, there exists $k$ such that for any $n$, there exists $a_{i_1}, a_{i_2} \in A^{(k)}$ such that $n = a_{i_1} + a_{i_2}$.
QED
Friday, November 22, 2013
1.1 Additive Properties of Sequences - Theorem 1.1.1 (L. G. Shnirelman)
The details in these notes are taken from A. O. Gelfond & Yu. V. Linnik, elementary methods in analytic number theory, 1965 (translated by Amiel Fienstein/Revised and edited by L. J. Mordell).
Definition 1: infinite sequence of integers
Let any capital Latin letter (e.g. $A$, $B$, $C$, ...) denote an infinite sequence where each term is distinct and in numerical order with the first term $0$.
For example, $A$ would represent:
$$0,a_1,a_2,a_3, \dots$$
where
$$0 < a_1 < a_2 < a_3 < \dots$$
Definition 2: number of terms not exceeding $n$
Let $A(n)$ be numerical function on sequences defined as the number of terms not exceeding $n$ so that:
$$A(n) = \sum_{0 < a_i \le n} 1$$
For example:
$$0\le\frac{A(n)}{n}\le1$$
Definition 3: infinitum (inf)
For a given set $S$, the greatest integer that is less than or equal to all elements in $S$.
Examples:
$$\inf\, \{1,2,3\}=1$$
$$\inf\, \{ x \in \mathbb{Z} : 0 < x < n \} = 1$$
Definition 4: density of a sequence
The density $d(A)$ of a sequence $A$ is defined as:
$$d(A) = \inf_n \frac{A(n)}{n}$$
Examples:
Theorem 1.1.1 (L. G. Shnirelman)
$$d(A+B) \ge d(A) + d(B) - d(A)d(B)$$
Proof:
(1) Let $C = A+B$ such that $c \in C$ implies $c = a + b$ where $a \in A, b \in B$
(2) Let $\alpha=d(A), \beta=d(B), \gamma=d(C)$
(3) There are $A(n)$ numbers in $A$ in the interval $[1,n]$ each of which appears in $C$ since $0 \in B$.
(4) Let $a_k, a_{k+1}$ be any two adjacent numbers in $A$.
(5) Let $l_k = a_{k+1}-a_k-1$, so that if $l_k > 0$, we have the following numbers not in $A$:
$$a_k+1, a_k+2, \dots, a_k+l_k = a_{k+1}-1$$
(6) For a given $a_k,a_{k+1}$, $B(l_k)$ is equal to count of the numbers in between $a_k$ and $a_{k+1}$ that are in $C$ since $1 \le r \le l_k$ and $r \in B$ implies that $a_k + r \in C$.
(7) From step(6), we have:
$$C(n) \ge A(n) + \sum_{k \le A(n)}{B(l_k)}$$
where each $l_k$ is taken from the intervals between numbers of the form $a_k$ and $a_{k+1}$
(8) For each $k$, $B(l_k) \ge \beta{l_k}$. [From Definition 4 above]
(9) So, from step(7), we have:
$$C(n) \ge A(N) + \beta\sum_{k \le A(n)}{l_k} = A(n) + \beta(n - A(n))$$
$$=A(n)(1 - \beta) + \beta{n} \ge \alpha(1 - \beta)n + \beta{n}$$
(10) For all $n \ge 1$, we have:
$$\gamma=d(A+B)=\inf_n\frac{C(n)}{n} \ge \alpha + \beta - \alpha\beta$$
QED
Corollary:
$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$
Proof:
(1) From Theorem 1.1.1 above:
$$1 - d(A+B) \le 1 - d(A) - d(B) + d(A)d(B) = (1 - d(A))(1 - d(B))$$
(2) So that:
$$d(A+B)-1 \ge -(1-d(A))(1-d(B))$$
(3) Which shows the case for $k=2$ where:
$$d(A+B) \ge 1 - (1 - d(A))(1 - d(B))$$
(4) Assume that it is true up to some $k \ge 2$ so that:
$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$
(5) Let $B = A_1 + \dots + A_k$
(6) From step(3) above, we have:
$$d(B + A_{k+1}) \ge 1 - (1 - d(B))(1 - d(A_{k+1}))$$
(7) From step(4), we have:
$$-d(B) \le -1 +\prod_{i=1}^{k}(1 - d(A_i))$$
(8) Which gives us:
$$1-d(B) \le \prod_{i=1}^{k}(1 - d(A_i))$$
(9) Combining step(8) with step(6) gives us:
$$d(A_1 + \dots + A_{k+1}) \ge 1 - \prod_{i=1}^k(1 - d(A_i))(1 - d(A_{k+1}))$$
QED
Definition 1: infinite sequence of integers
Let any capital Latin letter (e.g. $A$, $B$, $C$, ...) denote an infinite sequence where each term is distinct and in numerical order with the first term $0$.
For example, $A$ would represent:
$$0,a_1,a_2,a_3, \dots$$
where
$$0 < a_1 < a_2 < a_3 < \dots$$
Definition 2: number of terms not exceeding $n$
Let $A(n)$ be numerical function on sequences defined as the number of terms not exceeding $n$ so that:
$$A(n) = \sum_{0 < a_i \le n} 1$$
For example:
$$0\le\frac{A(n)}{n}\le1$$
Definition 3: infinitum (inf)
For a given set $S$, the greatest integer that is less than or equal to all elements in $S$.
Examples:
$$\inf\, \{1,2,3\}=1$$
$$\inf\, \{ x \in \mathbb{Z} : 0 < x < n \} = 1$$
Definition 4: density of a sequence
The density $d(A)$ of a sequence $A$ is defined as:
$$d(A) = \inf_n \frac{A(n)}{n}$$
Examples:
- if $1 \notin A$, then $d(A)=0$
- $d(A)=1$ if and only if $A$ contains all the positive integers.
- The densities of squares, cubes, and prime numbers equal $0$.
- $\forall{n}\, A(n) \ge n*d(A)$
Theorem 1.1.1 (L. G. Shnirelman)
$$d(A+B) \ge d(A) + d(B) - d(A)d(B)$$
Proof:
(1) Let $C = A+B$ such that $c \in C$ implies $c = a + b$ where $a \in A, b \in B$
(2) Let $\alpha=d(A), \beta=d(B), \gamma=d(C)$
(3) There are $A(n)$ numbers in $A$ in the interval $[1,n]$ each of which appears in $C$ since $0 \in B$.
(4) Let $a_k, a_{k+1}$ be any two adjacent numbers in $A$.
(5) Let $l_k = a_{k+1}-a_k-1$, so that if $l_k > 0$, we have the following numbers not in $A$:
$$a_k+1, a_k+2, \dots, a_k+l_k = a_{k+1}-1$$
(6) For a given $a_k,a_{k+1}$, $B(l_k)$ is equal to count of the numbers in between $a_k$ and $a_{k+1}$ that are in $C$ since $1 \le r \le l_k$ and $r \in B$ implies that $a_k + r \in C$.
(7) From step(6), we have:
$$C(n) \ge A(n) + \sum_{k \le A(n)}{B(l_k)}$$
where each $l_k$ is taken from the intervals between numbers of the form $a_k$ and $a_{k+1}$
(8) For each $k$, $B(l_k) \ge \beta{l_k}$. [From Definition 4 above]
(9) So, from step(7), we have:
$$C(n) \ge A(N) + \beta\sum_{k \le A(n)}{l_k} = A(n) + \beta(n - A(n))$$
$$=A(n)(1 - \beta) + \beta{n} \ge \alpha(1 - \beta)n + \beta{n}$$
(10) For all $n \ge 1$, we have:
$$\gamma=d(A+B)=\inf_n\frac{C(n)}{n} \ge \alpha + \beta - \alpha\beta$$
QED
Corollary:
$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$
Proof:
(1) From Theorem 1.1.1 above:
$$1 - d(A+B) \le 1 - d(A) - d(B) + d(A)d(B) = (1 - d(A))(1 - d(B))$$
(2) So that:
$$d(A+B)-1 \ge -(1-d(A))(1-d(B))$$
(3) Which shows the case for $k=2$ where:
$$d(A+B) \ge 1 - (1 - d(A))(1 - d(B))$$
(4) Assume that it is true up to some $k \ge 2$ so that:
$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$
(5) Let $B = A_1 + \dots + A_k$
(6) From step(3) above, we have:
$$d(B + A_{k+1}) \ge 1 - (1 - d(B))(1 - d(A_{k+1}))$$
(7) From step(4), we have:
$$-d(B) \le -1 +\prod_{i=1}^{k}(1 - d(A_i))$$
(8) Which gives us:
$$1-d(B) \le \prod_{i=1}^{k}(1 - d(A_i))$$
(9) Combining step(8) with step(6) gives us:
$$d(A_1 + \dots + A_{k+1}) \ge 1 - \prod_{i=1}^k(1 - d(A_i))(1 - d(A_{k+1}))$$
QED
Subscribe to:
Posts (Atom)