We apply the lower bound in Lemma 2.5.1 to the logarithms. For a typical term, we get $$ \ln \left(\frac{m+t-k}{m-k}\right) \geq \frac{\frac{m+t-k}{m-k}-1}{\frac{m+t-k}{m-k}}=\frac{t}{m+t-k} $$
证明 .
and so $$ \begin{aligned} \ln \left(\frac{m+t}{m}\right) &+\ln \left(\frac{m+t-1}{m-1}\right)+\cdots+\ln \left(\frac{m+1}{m-t+1}\right) \ & \geq \frac{t}{m+t}+\frac{t}{m+t-1}+\cdots+\frac{t}{m+1} . \end{aligned} $$ We replace each denominator by the largest one to decrease the sum: $$ \frac{t}{m+t}+\frac{t}{m+t-1}+\cdots+\frac{t}{m+1} \geq \frac{t^{2}}{m+t} . $$
For $n=1$ and $n=2$, if we require that $L_{n}$ be of the given form, then we get $$ L_{1}=1=a+b, \quad L_{2}=3=a \frac{1+\sqrt{5}}{2}+b \frac{1-\sqrt{5}}{2} $$ Solving for $a$ and $b$, we get $$ a=\frac{1+\sqrt{5}}{2}, \quad b=\frac{1-\sqrt{5}}{2} $$ Then $$ L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n} $$
translates into $$ c \cdot q^{n+1}=c \cdot q^{n}+c \cdot q^{n-1} $$ which after simplification becomes $$ q^{2}=q+1 $$
证明 .
So both numbers $c$ and $n$ disappear. ${ }^{1}$ So we have a quadratic equation for $q$, which we can solve and get $$ q_{1}=\frac{1+\sqrt{5}}{2} \approx 1.618034, \quad q_{2}=\frac{1-\sqrt{5}}{2} \approx-0.618034 . $$ This gives us two kinds of geometric progressions that satisfy the same recurrence as the Fibonacci numbers: $$ G_{n}=c\left(\frac{1+\sqrt{5}}{2}\right)^{n}, \quad G_{n}^{\prime}=c\left(\frac{1-\sqrt{5}}{2}\right)^{n} $$
(a) if $a \mid b$ and $b \mid c$ then $a \mid c$; (b) if $a \mid b$ and $a \mid c$ then $a \mid b+c$ and $a \mid b-c$; (c) if $a, b>0$ and $a \mid b$ then $a \leq b$; (d) if $a \mid b$ and $b \mid a$ then either $a=b$ or $a=-b$.
Unfortumately, the answer is yes. The smallest such number is $341=11 \cdot 31$. This is not a prime, but it satisfies $$ 341 \mid 2^{340}-1 . $$ (How do we know that this divisibility relation holds without extensive computation? We can use Fermat’s Theorem. It is sufficient to argue that both 11 and 31 are divisors of $2^{340}-1$, since then so is their product, 11 and 31 being different primes. By Fermat’s Theorem, $$ 11 \mid 2^{10}-1 $$
证明 .
Next we invoke the result : It implies that $$ 2^{10}-1 \mid 2^{340}-1 $$ Hence $$ 11 \mid 2^{340}-1 $$ For 31, we don’t need Fermat’s Theorem, but only again: $$ 31=2^{5}-1 \mid 2^{340}-1 $$
4.3.2. For $n=1$ and $n=2$, if we require that $L_{n}$ be of the given form, then we get $$ L_{1}=1=a+b, \quad L_{2}=3=a \frac{1+\sqrt{5}}{2}+b \frac{1-\sqrt{5}}{2} $$ Solving for $a$ and $b$, we get $$ a=\frac{1+\sqrt{5}}{2}, \quad b=\frac{1-\sqrt{5}}{2} $$ Then $$ L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n} $$
3.8.2. We apply the lower bound in Lemma 2.5.1 to the logarithms. For a typical term, we get $$ \ln \left(\frac{m+t-k}{m-k}\right) \geq \frac{\frac{m+t-k}{m-k}-1}{\frac{m+t-k}{m-k}}=\frac{t}{m+t-k} $$
证明 .
and so $$ \begin{aligned} \ln \left(\frac{m+t}{m}\right) &+\ln \left(\frac{m+t-1}{m-1}\right)+\cdots+\ln \left(\frac{m+1}{m-t+1}\right) \ & \geq \frac{t}{m+t}+\frac{t}{m+t-1}+\cdots+\frac{t}{m+1} \end{aligned} $$
For $n=1$ and $n=2$, if we require that $L_{n}$ be of the given form, then we get $$ L_{1}=1=a+b, \quad L_{2}=3=a \frac{1+\sqrt{5}}{2}+b \frac{1-\sqrt{5}}{2} $$ Solving for $a$ and $b$, we get $$ a=\frac{1+\sqrt{5}}{2}, \quad b=\frac{1-\sqrt{5}}{2} $$ Then $$ L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n} $$
This course covers the fundamentals of discrete mathematics with a focus on proof methods. Topics include: propositional and predicate logic, notation for modern algebra, naive set theory, relations, functions and proof techniques.
The number of elements of the set $X$, written $|X|$, is its cardinality. From the definition, $|{1,2,3}|=3$. Also, $|\varnothing|=0$. Definition 1.2 1. Given sets $X$ and $Y$, we say $X$ is a subset of $Y$ if every element of $X$ is also an element of $Y$. We write $X \subseteq Y$, and refer to the symbol $\subseteq$ as inclusion.
If there is an element of $Y$ that is not an element of $X$, we say that $X$ is a proper subset of $Y$, written $X \nsubseteq Y$. Note that if $X \varsubsetneqq Y$, then we also have that $X \subseteq Y$. Example $1.2$ The set $$ {1,3,4} \subseteq{1,2,3,4} $$ and it is also the case that $$ {1,3,4} \varsubsetneqq{1,2,3,4} $$
证明 .
These are two equations in two unknowns, and we solve them below Subtracting (1.4) from (1.3), we obtain $$ V_{1}(H)-V_{1}(T)=\Delta_{0}\left(S_{1}(H)-S_{1}(T)\right) $$ so that $$
We may put sets together using several operations. Definition $1.6$ Let $X$ and $Y$ be sets in a universe $U$.
The intersection of $X$ and $Y$, written $X \cap Y$, is the set consisting of elements in both $X$ and $Y$. We write $$ X \cap Y={u \in U: u \in X \text { and } u \in Y} $$
The union of $X$ and $Y$, written $X \cup Y$, is the set consisting of elements in $X$ or $Y$. We write $$ X \cup Y={u \in U: u \in X \text { or } u \in Y} $$
The difference of $X$ with $Y$, written $X \backslash Y$, is the set consisting of elements in $X$ but not in $Y$. We write $$ X \backslash Y={u \in U: u \in X \text { and } u \notin Y} $$
The complement of $X$, written $X^{c}$, is the set of elements of $U$ not in $X$. We write $$ X^{c}={u \in U: u \notin X} $$
Definition 1.1. A statement (or proposition) is a sentence that is either true or false but not both. Examples of statements:
$p=$ “Alice is 12 years old”,
$q=$ “Bob ate pizza for dinner yesterday”,
$r=” 3 \cdot 3=9$ “,
$s=” 2 \cdot 4=9 “$. Examples of non-statements:
“Is the sky blue?” (question)
” $x^{2}+y^{2}=13 “$ (for some values of $x$ and $y$ the proposition is true, whereas for others it is false). Compound Statements We can make new statement from old ones using operators like “not”, “and”, “or”, “if then”. There are a few simple examples:
“Alice is not 12 years old” $(\sim p)$,
“Bob ate pizza for dinner yesterday and $3 \cdot 3=9$ ” $(q \wedge r)$. Compound statements (since they are (regular) statements as well) must have well-defined truth values – they must be either true or false. We can write down a table of truth values for compound statements based on the truth values of component statements. Definition 1.2. The negation of a statement $p$ (denoted $\sim p$ ) is true if $p$ is false. If $p$ is true, then $\sim p$ is false.
