# Understanding these basic definition and statement~

• Mathematical induction is a method of proof used to establish that a given statement is true for all natural numbers. Let $S(n)$ be a statement about the positive integer $n .$ If
1. $S(1)$ is true and
2. for all $k \geq 1$, the truth of $S(k)$ implies the truth of $S(k+1)$,
then $S(n)$ is true for all $n \geq 1$ Verifying $S(1)$ is true is called the basis step. The assumption that $S(k)$ is true for some $k \geq 1$ is called the induction hypothesis. Using the induction hypothesis to prove $S(k+1)$ is true is called the induction step. There are variants of mathematical induction used in practice, for example if one wants to prove a statement not for all natural numbers but only for all numbers greater than or equal to a certain number $b$, then
3. Show $S(b)$ is true.
4. Assume $S(m)$ is true for $m \geq b$ and show that truth of $S(m)$ implies the truth of $S(m+1)$
Another generalization, called strong induction, says that in the inductive step we may assume not only the statement holds for $S(k+1)$ but also that it is true for $S(m)$ for all $m \leq k+1$. In strong induction it is not necessary to list the basis step, it is clearly true that the statement holds for all previous cases. The inductive step of a strong induction in this case corresponds to the basis step in ordinary induction.
• Let $A$ be a nonempty subset of $\mathbb{R}$. The number $b$ is called an upper bound for $A$ if for all $x \in A$, we have $x \leq b$. A number $b$ is called a least upper bound of $A$ if, first, $b$ is an upper bound for $A$ and, second, $b$ is less than or equal to every upper bound for $A$. The supremum of $A$ (also called least upper bound of $A$ ) is denoted by $\sup (A), \sup A$ or $\operatorname{lub}(A)$. If $A \subset \mathbb{R}$ is not bounded above, we say that $\sup A$ is infinite and write $\sup A=+\infty$.
• A lower bound for a set $A \subset \mathbb{R}$ is a number $b$ such that $b \leq x$ for all $x \in A$. Also $b$ is called a greatest lower bound if and only if it is a lower bound and for any lower bound $c$ of $A$, $c \leq b .$ The infimum of $A$ (also called greatest lower bound of $A$ ) is denoted by inf $(A), \inf A$ or $g l b(A)$. If $A \subset \mathbb{R}$ is not bounded below, we set $\inf A=-\infty$.
• Well-Ordering Property: If $A$ is a nonempty subset of $\mathbb{N}$, then there is a smallest element in $A$, i.e., there is an $a \in A$ such that $a \leq x$ for every $x \in A$.
• Archimedean Property: If $x \in \mathbb{Q}$, then there is an integer $n$ with $x<n .$
• For each $n \in \mathbb{N}$, let $I_{n}$ be a nonempty closed interval in $\mathbb{R} .$ The family $\left{I_{n}: n \in \mathbb{N}\right}$ is called a nest of intervals if the following conditions hold:
• $I_{n+1} \subset I_{n}$ for all $n \in \mathbb{N}$
• For each $\varepsilon>0$, there is some $n \in \mathbb{N}$ such that $\left|I_{n}\right|<\varepsilon$.

# Try the following problem to test yourself！

Problem 1.

Prove that $\sqrt{2}$ is not rational.

Proof .

Assume not. Let $r \in \mathbb{Q}$ such that $r=\sqrt{2}$ or $r^{2}=2 .$ Without loss of generality, we may assume $r \geq 0$. And since $r^{2}=2$, we have $r>0$. Since $r$ is rational, there exist two natural numbers $n \geq 1$ and $m \geq 1$ such that
$$r=\frac{n}{m} .$$
Moreover one may assume that $n$ and $m$ are relatively prime, i.e., the only common divisor is $1 .$ Since $r^{2}=2$, we get
$$\left(\frac{n}{m}\right)^{2}=\frac{n^{2}}{m^{2}}=2$$
which implies $2 m^{2}=n^{2}$. Therefore, $n^{2}$ is even, so it is a multiple of $2 .$ Assume that $n$ is not even, then $n=2 k+1$ for some natural number $k$. Hence $n^{2}=4 k^{2}+4 k+1=2\left(2 k^{2}+2 k\right)+1$. In other words, if $n$ is not even, then $n^{2}$ will not be even. Therefore, $n$ is also even. Set $n=2 k$ for some natural number $k$. Then $n^{2}=4 k^{2}$ and since $n^{2}=2 m^{2}$, we deduce that $m^{2}=2 k^{2}$. The same previous argument will imply that $m$ is also even. So both $n$ and $m$ are even so both are multiples of 2 . This is a contradiction with our assumption that both are relatively prime. Therefore, such a rational number $r$ does not exist which completes the proof of our statement.

Problem 2.

Show that two real numbers $x$ and $y$ are equal if and only if $\forall \varepsilon>0$ it follows that $|x-y|<\varepsilon$

Proof .

This is an if and only if statement, and we need to prove the implications in both directions. $(\Rightarrow):$ If $x=y$, then $|x-y|=0$ and thus $|x-y|<\varepsilon$ no matter what $\varepsilon>0$ is chosen. $:(\Leftarrow)$ We give a proof by contradiction. Assume $x \neq y$, then $\varepsilon_{0}=|x-y|>0$. However, the statements
$$|x-y|=\varepsilon_{0} \text { and }|x-y|<\varepsilon_{0}$$
cannot be both true, our assumption is wrong, thus $x=y$.

Problem 3.

Use the induction argument to prove that
$$1^{2}+2^{2}+\cdots+n^{2}=\frac{2 n^{3}+3 n^{2}+n}{6}$$
for all natural numbers $n \geq 1$.

Proof .

Since
$$1^{2}=\frac{2+3+1}{6},$$
the above identity holds in the case $n=1$. Assume that the identity holds for $n$ and let us prove that it also holds for $n+1$. Since
$$1^{2}+2^{2}+\cdots+(n+1)^{2}=1^{2}+2^{2}+\cdots+n^{2}+(n+1)^{2},$$
the induction assumption implies
$$1^{2}+2^{2}+\cdots+(n+1)^{2}=\frac{2 n^{3}+3 n^{2}+n}{6}+(n+1)^{2} .$$
Algebraic manipulations imply
\begin{aligned} \frac{2 n^{3}+3 n^{2}+n}{6}+(n+1)^{2} &=\frac{2 n^{3}+3 n^{2}+n+6(n+1)^{2}}{6} \ &=\frac{2 n^{3}+3 n^{2}+n+3(n+1)^{2}+3(n+1)^{2}}{6} \ &=\frac{2 n^{3}+6 n^{2}+7 n+3+3(n+1)^{2}}{6} . \end{aligned}
On the other hand, we have
\begin{aligned} \frac{2(n+1)^{3}+3(n+1)^{2}+(n+1)}{6} &=\frac{2 n^{3}+6 n^{2}+6 n+2+3(n+1)^{2}+(n+1)}{6} \ &=\frac{2 n^{3}+6 n^{2}+7 n+3+3(n+1)^{2}}{6} \end{aligned}
which implies
$$1^{2}+2^{2}+\cdots+(n+1)^{2}=\frac{2(n+1)^{3}+3(n+1)^{2}+(n+1)}{6} .$$
So our identity is also valid for $n+1$. By induction we clearly showed that the identity is valid for any natural number $n \geq 1$.

Fourier analysis代写

## 离散数学代写

Partial Differential Equations代写可以参考一份偏微分方程midterm答案解析