w2

w2.pdf

Prove that the function $f: \mathbb{N} \rightarrow \mathbb{Z}$ defined by

\[ f(n)=\begin{cases}\frac{n}{2} & \text{ if }n\text{ is even }\\ -\frac{n-1}{2} & \text{ if }n\text{ is odd }\end{cases}\text{ \textasciitilde\textasciitilde\textasciitilde\textasciitilde is a bijection} \]

Proof

We need to demonstrate that $f$ is both injective and surjective.
1. Injectivity
  
  To show that $f$ is injective, assume that $f(n_1) = f(n_2)$ for some $n_1, n_2 \in \mathbb{N}$. We need to prove that $n_1 = n_2$.
  
  Case 1: Both $n_1$ and $n_2$ are even.
  
  $f(n_1) = \frac{n_1}{2}, \quad f(n_2) = \frac{n_2}{2}$$\frac{n_1}{2} = \frac{n_2}{2} \implies n_1 = n_2$
  
  Case 2: Both $n_1$ and $n_2$ are odd.
  
  $f(n_1) = -\frac{n_1 - 1}{2}, \quad f(n_2) = -\frac{n_2 - 1}{2}$$-\frac{n_1 - 1}{2} = -\frac{n_2 - 1}{2} \implies \frac{n_1 - 1}{2} = \frac{n_2 - 1}{2} \implies n_1 - 1 = n_2 - 1 \implies n_1 = n_2$
  
  Case 3: One is even and the other is odd.
  
  Assume $n_1$ is even and $n_2$ is odd.
  
  $f(n_1) = \frac{n_1}{2}, \quad f(n_2) = -\frac{n_2 - 1}{2}$$\frac{n_1}{2} = -\frac{n_2 - 1}{2} \implies n_1 = -(n_2 - 1)$Since $n_1$ is a natural number (assuming $\mathbb{N}$ starts at 1), the right side $-(n_2 - 1)$ must also be a natural number. However, $-(n_2 - 1)$ is non-positive, which contradicts $n_1 \geq 1$. Thus, this case is impossible.
  
  Conclusion: $f$ is injective because $f(n_1) = f(n_2)$ implies $n_1 = n_2$.
2. Surjectivity
  
  To show that $f$ is surjective, we need to demonstrate that for every integer $z \in \mathbb{Z}$, there exists a natural number $n \in \mathbb{N}$ such that $f(n) = z$.
  
  Case 1: $z \geq 0$.
  
  Let $z$ be a non-negative integer.
  - If $z = 0$, choose $n = 1$:$f(1) = -\frac{1 - 1}{2} = 0$
  - If $z > 0$, choose $n = 2z$ (which is even):$f(2z) = \frac{2z}{2} = z$
  Case 2: $z < 0$.
  
  Let $z = -k$ where $k$ is a positive integer.
  
  Choose $n = 2k + 1$ (which is odd):
  
  $f(2k + 1) = -\frac{(2k + 1) - 1}{2} = -\frac{2k}{2} = -k = z$Conclusion: For every $z \in \mathbb{Z}$, there exists a natural number $n$ such that $f(n) = z$. Therefore, $f$ is surjective.
Hence, $f$ is bijective

‍

Let $X$ be a non-empty subset of $\mathbb{Z}$ which has no least member. Show that we can choose a sequence $x_{1}, x_{2}, \ldots, x_{n}, \ldots$ of distinct members of $X$ such that $x_{n}<x_{n-1}$ for all $n \in \mathbb{N}$. Deduce that $X$ is infinite.

Use WOP

Let's consider a set $A=\left\lbrace \exists n_0\text{ such that we cannot choose a decreasing sequence }x_1,x_2,...,x_n,...\right\rbrace$

We need to prove $A=\emptyset$, suppose $A\neq \emptyset$

Then $n_0$ is the first element in $A$ and $n_0-1\notin A$

We have $X=\{x_1,x_2,\ldots,x_{n_0-1}\}$ is decreasing.

Since $X$ has no least number, then we can choose $x_{n_0}<x_{n_0-1}$.

Thus $X=\{x_1,x_2,\ldots,x_{n_0-1},x_{n_0}\}$ is still decreasing.

Hence $n_0\notin A$ , which is contradiction to $n_0$ is the first element in $A$

Therefore, we can choose a sequence $x_{1}, x_{2}, \ldots, x_{n}, \ldots$ of distinct members of $X$ such that $x_{n}<x_{n-1}$ for all $n \in \mathbb{N}$

‍

In the lectures, it's been seen that it may happen that $Y \subsetneq X$ while $|X|=|Y|$. Show that this is not possible if $X$ is finite.

Proof

Suppose $X$ is finite, which means there exists an injection $f:X\rightarrow N_{m}\left(m\in \N\right)$

Since $|X|=|Y|$, then there exists a bijection $l:Y\rightarrow X$

Then $l\circ f:Y\rightarrow N_{m}$ is injective, which means $Y$ is finite.

Since $X$ and $Y$ are finite and $Y\subsetneq X$, then $|X|>|Y|$

Which is contradiction to $|X|=|Y|$
Let $n \in \mathbb{N}$. Let $A_{1}, A_{2}, \ldots A_{n}$ be $n$ pairwise disjoint finite sets. Then $\left|A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right|=\left|A_{1}\right|+$ $\left|A_{2}\right|+\cdots+\left|A_{n}\right|$

Proof
1. Consider the Union
  $A_{1} \cup A_{2} \cup \cdots \cup A_k \cup A_{k+1} = \left( A_{1} \cup A_{2} \cup \cdots \cup A_k \right) \cup A_{k+1}$
2. Apply the Base Case for Two Sets:
  From the earlier discussion, we know that for two disjoint finite sets $B$ and $C$,
  $|B \cup C| = |B| + |C|$Here, let:
  - $B = A_{1} \cup A_{2} \cup \cdots \cup A_k$
  - $C = A_{k+1}$
  Note: Since $A_{k+1}$ is disjoint from each $A_i$ for $i = 1, 2, \ldots, k$, it is disjoint from their union $B$. 3. Apply the Inductive Hypothesis and the Base Case:
  
  $$ \begin{aligned} \left|A_{1} \cup A_{2} \cup \cdots \cup A_k \cup A_{k+1}\right| &= |B \cup C| \ &= |B| + |C| \quad \text{(since $ B $ and $ C $ are disjoint)} \ &= \left|A_{1} \cup A_{2} \cup \cdots \cup A_k\right| + |A_{k+1}| \ &= \left( |A_1| + |A_2| + \cdots + |A_k| \right) + |A_{k+1}| \quad \text{(by the Inductive Hypothesis)} \ &= |A_1| + |A_2| + \cdots + |A_k| + |A_{k+1}| \end{aligned} $$ 4. Conclusion of the Inductive Step:
  Therefore, if the statement holds for $k$ sets, it also holds for $k + 1$ sets.
By mathematical induction, the statement holds for all natural numbers $n$. That is, for any $n$ pairwise disjoint finite sets $A_1, A_2, \ldots, A_n$,

$\left|A_{1} \cup A_{2} \cup \cdots \cup A_n\right| = \left|A_{1}\right| + \left|A_{2}\right| + \cdots + \left|A_n\right|$
Let $\left(A_{i}\right)_{i \in \mathbb{N}}$ be any sequence of nonempty finite sets. Is their cartesian product, $A_{1} \times A_{2} \times A_{3} \times \cdots$, countable? ${ }^{1}$ Justify your answer.

No, the infinite Cartesian product $A_1 \times A_2 \times A_3 \times \cdots$ of nonempty finite sets is generally uncountable.

Justification:
1. Understanding the Infinite Product:Each $A_i$ is a nonempty finite set. The infinite Cartesian product $\prod_{i=1}^\infty A_i$ consists of all sequences $(a_1, a_2, a_3, \dots)$ where $a_i \in A_i$ for each $i \in \mathbb{N}$.
  - Case 1: Infinitely Many $A_i$ Have Size $\geq 2$
  - Example: Let each $A_i = \{0, 1\}$. Then the Cartesian product $\prod_{i=1}^{\infty} A_i$ is equivalent to the set of all infinite binary sequences.
  - Uncountability: Using Cantor's diagonal argument, we can show that the set of all infinite binary sequences is uncountable.
    - Cantor's Diagonal Argument: Assume, for contradiction, that the set is countable. Then, we can list all binary sequences. Construct a new binary sequence by flipping the $i$-th bit of the $i$-th sequence in the list. This new sequence differs from every sequence in the list at least at one position, leading to a contradiction. Hence, the set is uncountable. - Conclusion: If infinitely many $A_i$ have at least two elements, the Cartesian product $A_{1} \times A_{2} \times \cdots$ is uncountable. - Case 2: Only Finitely Many $A_i$ Have Size $\geq 2$
  - If all but finitely many $A_i$ are singleton sets (i.e., $|A_i| = 1$ for sufficiently large $i$), then the infinite product reduces to a finite product times a singleton, which is effectively finite.
  - Conclusion: In this scenario, the Cartesian product is finite and hence countable.
    1. Conclusion:
  - General Case: The infinite product is uncountable if infinitely many $A_i$ have more than one element.
  - Specific Case: It is countable (even finite) only if all but finitely many $A_i$ are singleton sets.
Therefore, the infinite Cartesian product of nonempty finite sets is uncountable in general.

Answer: No; because when infinitely many sets have more than one element, their infinite product is uncountable.

‍

Prove that the following inequalities are valid $\forall n \in \mathbb{N}$
(a) $3^{n}+5^{n} \geq 2^{n+2}$
(b) $3^{n} \geq n^{3}$
(e) $\sum_{i=1}^{2^{n}} \frac{1}{2 i-1}>\frac{n+3}{4}$
(c) $\sum_{i=1}^{n} \frac{n+i}{i+1} \leq 1+n(n-1)$
(f) $\sum_{i=1}^{n} \frac{1}{i!} \leq 2-\frac{1}{2^{n-1}}$
(d) $\sum_{i=n}^{2 n} \frac{i}{2^{i}} \leq n$
(g) $\prod_{i=1}^{n} \frac{4 i-1}{n+i} \geq 1$
1. $3^{n} + 5^{n} \geq 2^{n+2}$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $3^1 + 5^1 = 3 + 5 = 8 \geq 8 = 2^{1+2}$
  
  Inductive Step: Assume $3^{k} + 5^{k} \geq 2^{k+2}$.
  
  For $n = k+1$: $3^{k+1} + 5^{k+1} = 3 \cdot 3^{k} + 5 \cdot 5^{k} \geq 3 \cdot 2^{k+2} + 5 \cdot 2^{k+2} = 8 \cdot 2^{k+2} = 2^{k+3}$
  
  Thus, $3^{k+1} + 5^{k+1} \geq 2^{(k+1)+2}$. 2. $3^{n} \geq n^{3}$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $3^1 = 3 \geq 1 = 1^{3}$
  
  Inductive Step: Assume $3^{k} \geq k^{3}$.
  
  For $n = k+1$: $3^{k+1} = 3 \cdot 3^{k} \geq 3 \cdot k^{3}$
  
  We need to show $3k^{3} \geq (k+1)^{3}$: $3k^{3} \geq k^{3} + 3k^{2} + 3k + 1 \implies 2k^{3} \geq 3k^{2} + 3k + 1$
  
  This holds for $k \geq 2$. 3. $\sum_{i=1}^{n} \frac{n+i}{i+1} \leq 1 + n(n-1)$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $\frac{1+1}{1+1} = 1 \leq 1 + 1(1-1) = 1$
  
  Inductive Step: Assume $\sum_{i=1}^{k} \frac{k+i}{i+1} \leq 1 + k(k-1)$.
  
  For $n = k+1$: $\sum_{i=1}^{k+1} \frac{(k+1)+i}{i+1} = \sum_{i=1}^{k} \frac{k+1+i}{i+1} + \frac{2k+2}{k+2} \leq 1 + k(k-1) + \frac{2k+2}{k+2}$ 4. $\sum_{i=n}^{2n} \frac{i}{2^{i}} \leq n$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $\frac{1}{2} + \frac{2}{4} = \frac{1}{2} + \frac{1}{2} = 1 \leq 1$
  
  Inductive Step: Assume $\sum_{i=k}^{2k} \frac{i}{2^{i}} \leq k$.
  
  For $n = k+1$: $\sum_{i=k+1}^{2(k+1)} \frac{i}{2^{i}} \leq (k+1)$ (by bounding each term and summing)
2. $\sum_{i=1}^{2^{n}} \frac{1}{2i-1} > \frac{n+3}{4}$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $\frac{1}{1} + \frac{1}{3} = \frac{4}{3} > \frac{1+3}{4} = 1$
  
  Inductive Step: Assume $\sum_{i=1}^{2^{k}} \frac{1}{2i-1} > \frac{k+3}{4}$.
  
  For $n = k+1$: $\sum_{i=1}^{2^{k+1}} \frac{1}{2i-1} = \sum_{i=1}^{2^{k}} \frac{1}{2i-1} + \sum_{i=2^{k}+1}^{2^{k+1}} \frac{1}{2i-1} > \frac{k+3}{4} + \text{additional positive terms} > \frac{(k+1)+3}{4}$ 6. $\sum_{i=1}^{n} \frac{1}{i!} \leq 2 - \frac{1}{2^{n-1}}$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $\frac{1}{1!} = 1 \leq 2 - \frac{1}{2^{0}} = 1$
  
  Inductive Step: Assume $\sum_{i=1}^{k} \frac{1}{i!} \leq 2 - \frac{1}{2^{k-1}}$.
  
  For $n = k+1$: $\sum_{i=1}^{k+1} \frac{1}{i!} \leq \left(2 - \frac{1}{2^{k-1}}\right) + \frac{1}{(k+1)!} \leq 2 - \frac{1}{2^{k}} \quad \text{(since } \frac{1}{(k+1)!} \leq \frac{1}{2^{k}})$ 7. $\prod_{i=1}^{n} \frac{4i-1}{n+i} \geq 1$ for all $n \in \mathbb{N}$
  
  Base Case ($n = 1$): $\frac{4(1)-1}{1+1} = \frac{3}{2} \geq 1$
  
  Inductive Step: Assume $\prod_{i=1}^{k} \frac{4i-1}{k+i} \geq 1$.
  
  For $n = k+1$: $\prod_{i=1}^{k+1} \frac{4i-1}{(k+1)+i} = \left(\prod_{i=1}^{k} \frac{4i-1}{k+i}\right) \cdot \frac{4(k+1)-1}{2k+1} \geq 1 \cdot \frac{4k+3}{2k+1} \geq 1 \quad \text{(since } 4k+3 \geq 2k+1)$
strategy: 归纳法之后放缩至题目的形式

常见技巧:1. $n!>2^n$ 2. 函数增长速度

‍
Let $\left(a_{n}\right)_{n \in \mathbb{N}}$ be the sequence of real numbers defined recursively as $a_{1}=2, \quad a_{n+1}=2 n a_{n}+2^{n+1} n!, \quad \forall n \in \mathbb{N}$. Prove that $a_{n}=2^{n} n!$.
Let $\left(a_{n}\right)_{n \in \mathbb{N}}$ be the sequence of real numbers defined recursively as $a_{1}=0 \quad a_{n+1}=a_{n}+n(3 n+1), \quad \forall n \in \mathbb{N}$. Prove that $a_{n}=n^{2}(n-1)$.

Since the result is too complex that are different from A.P./G.P., thus we should use induction to prove it easily.

‍

Prove that any natural number $n$ can be written as a sum of distinct powers of 2 (including $2^{0}=1$ ).

The statement is obviously true for $n = 0$.

Assume that we are given an $n \geq 1$ and that it is true for all $m$ with $0 \leq m < n$.

When $n = 2m$ then $m < n$ and therefore $m = \sum_k 2^{p_k}$ with finitely many $p_k$, all of them different. It follows that $n = \sum_k 2^{p_k+1}$ with all $p_k + 1$ different.

When $n = 2m + 1$ with an $m$ as before then $n = 2^0 + \sum_k 2^{p_k+1}$ with all $p_k + 1$ different and different from 0.

‍

Method: Induction

Strategy: 分类讨论观察形式是多个2的幂相加那么分类讨论时候已知n去推n+1可能并不是一个好的选择因此用强归纳看看

观察到与2有关乘以2保持的原有的形式

‍

(Exercise 3, from Biggs 1.1) Prove that if any two integers $a$ and $b$ are given, then there is an integer $c$ such that $(a+b) c=a^{2}-b^{2}$.

此题需要等号两边消去相同项不要忘记讨论是否为0

‍

Let $a$ and $b$ be positive integers and let $d=\operatorname{gcd}(a, b)$. Prove that there are integers $x$ and $y$ for which $a x+b y=c$ if and only if $d \mid c$.

Strategy: when you see gcd, donnot forget use Bézout's Theorem

‍

Show that in any set of 12 integers there are two whose difference is divisible by 11.

Method: Pigeonhole principle

Strategy: divisible hint me to use divisibility. Then you can naturally consider congruence

Proof:

Consider any set of 12 integers, denoted as $a_1, a_2, \dots, a_{12}$.

Divide each $a_i$ by 11, yielding a remainder $r_i$, where $r_i \in \{0, 1, 2, \dots, 10\}$, giving 11 possible remainders.

By the pigeonhole principle, mapping 12 integers to 11 remainder classes guarantees that at least two integers, say $a_i$ and $a_j$, must have the same remainder, i.e., $r_i = r_j$.

Thus, $a_i - a_j$ is divisible by 11, as:

$a_i - a_j \equiv r_i - r_j = 0 \ (\text{mod} \ 11).$Hence, in any set of 12 integers, there are two whose difference is divisible by 11.

‍

Let $d=\operatorname{gcd}(a, b)$. Which are the possible values for $\operatorname{gcd}(a+b, 2 b-a)$ ? Give examples in which $\operatorname{gcd}(a+b, 2 b-a)$ equals each of these possibilities.

5.Theorem of Euclidean Algorithm 求解最大公因数

6.Bézout's Theorem 裴蜀定理表示最大公因数

If a\mid b and a\mid c then a\mid(\alpha b+\beta c) with \alpha,\beta\in\Z 化简最大公因数

最大公因数的三种方法
Let $x, y \in \mathbb{Z}$. Prove that if $x^{2}+y^{2}$ is divisible by 3 then $x$ and $y$ are both divisible by 3 .
Prove that there are no integers $x, y, z, t \in \mathbb{Z}$ for which $x^{2}+y^{2}-3 z^{2}-3 t^{2}=0$ unless all of them are 0 .

‍