5.1 数列

数列

数列(sequence)是一个函数,其定义域是两个给定整数之间的所有整数，或者大于等于某个给定整数的所有整数.

通常将一个数列表示为一排元素的集合,记为 $$ a_m,a_{m+1},a_{m+2},\cdots,a_n $$ 每个元素$a_k$称为一项(term), $a_k$中的$k$称为下标(subscript)或索引(index)

$m$是首项的下标,而$n$则是末项的下标.

无穷数列可以表示为: $$ a_m,a_{m+1},a_{m+2},\cdots $$ 数列的通项公式或显式公式表示项 $a_k$的值与下标$k$之间的关系.

不同的通项公式可能会产生元素相同的数列

求和符号

求和符号$\sum\limits_m^n a_k$表示$a_m,a_{m+1},a_{m+2},\cdots,a_n$的和,$a_m,a_{m+1},a_{m+2},\cdots,a_n$被称为求和的展开式(expand form),记为: $$ \sum_m^n a_k=a_m,a_{m+1},a_{m+2},\cdots,a_n $$ $k$被称为求和下标,$m$是求和的下限,$n$是求和上限.

乘积符号

乘积符号$\prod\limits_{m}^{n} a_k$表示$a_m\cdot a_{m+1}\cdot a_{m+2}\cdot \cdots\cdot a_n$的积记为: $$ \prod_m^n a_k=a_m\cdot a_{m+1}\cdot a_{m+2}\cdot \cdots\cdot a_n $$ 一些性质

$\sum\limits_m^n a_k+\sum\limits_m^n b_k=\sum\limits_m^n(a_k+b_k)$
$c\cdot\sum\limits_m^n a_k=\sum\limits_m^n(c\cdot a_k)$
$\left(\prod_m^n a_k\right)\left(\prod_m^n b_k\right)=\prod_m^n(a_k\cdot b_k)$

阶乘与组合数

正整数$n$的阶乘记作$n!$,定义为从$1$到$n$,所有正整数的乘积 $$ n!=n\cdot(n-1)\cdots3\cdot2\cdot1 $$

$0$的阶乘定义为$1$,即$0!=1$

阶乘的递归定义

阶乘还可以递归的定义为 $$ n!= \begin{cases} 1 & \text{if } n=0 \\ n(n-1)! & \text{if } n\ge1 \end{cases} $$

对于整数$n$和$r$($0\le r\le n$),符号 $$ \binom{n}{r} $$ 表示从一个$n$个元素的集合选择出具有$r$的元素的子集的个数.其中 $$ \binom{n}{r}=\frac{n!}{r!\cdot(n-r)!} $$

组合数计算的例子

例1例2例3

\[ \begin{align*} \binom{8}{5}=&\frac{8!}{5!\cdot(8-5)!} \\ =&\frac{8\cdot7\cdot\cancel{6}\cdot\cancel{5!}}{\cancel{5!}\cdot\cancel{3\cdot2}\cdot1} \\ =&56 \end{align*} \]

\[ \begin{align*} \binom{4}{4}=&\frac{4!}{4!\cdot(4-4)!} \\ =&\frac{\cancel{4!}}{\cancel{4!}\cdot1} \\ =&1 \end{align*} \]

\[ \begin{align*} \binom{n+1}{n}=&\frac{(n+1)!}{n!\cdot((n+1)-n)!} \\ =&\frac{(n+1)\cdot\cancel{n!}}{\cancel{n!}\cdot1} \\ =&n+1 \end{align*} \]

5.2 数学归纳法

数学归纳法

演绎(deduction)是指使用逻辑推理法则从一般原理推断出结论,归纳则是指在观察到某一规律在大量具体实例中均成立后，总结出一个一般性原则.

数学归纳法是一种演绎而不是归纳,它实际上是一种基于自然数良序性质的演绎推理，不依赖于经验观察，而是通过"基本步+归纳步"的逻辑链条证明所有自然数都满足命题

假设$P(n)$是一个关于整数$n$的命题,而$a$是一个固定的整数,数学归纳法原理(The principle of mathematical induction)指的是,如果满足以下两个条件

$P(a)$为真
对于任意整数$k\ge a$,如果$P(k)$为真,那么$P(k+1)$也为真

那么对于任意的整数$n\ge a$,$P(n)$为真.

数学归纳法可用于证明形如"对于任意的$n\ge a$的整数,$P(n)$为真"的命题.在使用数学归纳法时,需要完成以下两个步骤

基本步骤(basis step):说明$P(a)$为真
归纳步骤(inductive step):说明对于任意整数$k\ge a$,如果$P(k)$为真,那么$P(k+1)$也为真

在进行归纳步骤时,首先假设$P(k)$为真(这个假设被称为推理假设(inductive hypothesis)),然后利用推理假设推导出$P(k+1)$.一般就是将$P(k+1)$往$P(k)$的形式上凑.

数学归纳法的直观理解

数学归纳法可以用多米诺骨牌倒下的过程来形象地表示.基本步骤就像是推倒了第$a$张骨牌,而归纳步骤就像是说明每一张骨牌倒下都会推倒下一张骨牌.因此,如果基本步骤和归纳步骤都成立,那么所有的骨牌都会被推倒.

下面来看几个利用数学归纳法进行证明的例子

数学归纳法证明的例子

前$n$项整数的和

使用数学归纳法证明

\[ 1+2+\cdots+n=\frac{n(n+1)}{2}, n\ge1 \]

    本题要证明的命题$P(n)$是$1+2+\cdots+n=\dfrac{n(n+1)}{2}, n\ge1$.

    对于基本步骤, 需要证明$P(1)$为真,将$P(n)$中的$n$替换为$1$,得到
    $$
    1=\frac{1\cdot(1+1)}{2}=1
    $$
    显然,$P(1)$为真.   
    接着,来看归纳步骤.假设$P(k), k\ge1$为真,即
    $$
    1+2+\cdots+k=\frac{k(k+1)}{2}
    $$
    需要证明$P(k+1)$为真,即$1+2+\cdots+(k+1)=\dfrac{(k+1)(k+2)}{2}$为真.
    $$
    \begin{aligned}
    1+2+\cdots+k+(k+1)&=\frac{k(k+1)}{2}+(k+1) \\\\
    &=\frac{k(k+1)+2(k+1)}{2} \\\\
    &=\frac{(k+1)(k+2)}{2}
    \end{aligned}
    $$    
    所以$P(k+1)$为真.$\blacksquare$

=== "证明整除性"
    使用数学归纳法证明$2^{2n}-1, n\ge0$可以被$3$整除

    本题要证明的命题$P(n)$是$3\mid 2^{2n}-1, n\ge0$.
    对于基本步骤, 需要证明$P(0)$为真,将$P(n)$中的$n$替换为$0$,得到
    $$
    2^0-1=0=0\cdot3
    $$
    根据整除性的定义,$P(0)$为真.
    接着,来看归纳步骤.假设$P(k), k\ge0$为真,即
    $$
    2^{2k}-1\text{可以被}3\text{整除}
    $$
    根据整除性的定义,令$2^{2k}-1=3r$,$r$为整数.
    我们需要证明$P(k+1)$为真,即$2^{2(k+1)}-1$可以被$3$整除.
    $$
    \begin{aligned}
    2^{2(k+1)}-1&=2^{2k}\cdot2^2-1 \\\\
    &=2^{2k}(3+1)-1 \\\\
    &=3\cdot2^{2k}+2^{2k}-1 \\\\
    &=3\cdot2^{2k}+3r \\\\
    &=3(2^{2k}+r)
    \end{aligned}
    $$
    因为$2^{2k}+r$是整数,所以$2^{2(k+1)}-1$可以被$3$整除.
    所以$P(k+1)$为真.$\blacksquare$

=== "证明不等式"
    使用数学归纳法证明对任意大于等于$3$的整数$n$, 
    $$
    2n+1<2^n
    $$

    本题要证明的命题$P(n)$是$2n+1<2^n,n\ge3$.
    对于基本步骤, 需要证明$P(3)$为真,将$P(n)$中的$n$替换为$3$,得到
    $$
    2\cdot3+1=7<2^3=8
    $$
    显然,$P(3)$为真.
    接着,来看归纳步骤.假设$P(k), k\ge3$为真,即
    $$
    2k+1<2^k
    $$
    我们需要证明$P(k+1)$为真,即$2(k+1)+1<2^{k+1}$.
    $$
    \begin{aligned}
    2(k+1)+1&=(2k+1)+2 \\\\
    &<2^k+2 \\\\
    &<2^k+2^k \\\\
    &<2^{k+1}
    \end{aligned}
    $$
    所以$P(k+1)$为真.$\blacksquare$

=== "Trominoes问题"
    Trominoes是由三个正方形组成的图形,包括两种类型,如下图所示
    <figure markdown="span">
    ![Trominoes](Chapter5%20Squence/images/trominoes.webp){ height="100" }
    <figcaption>Trominoes的两种类型</figcaption>
    </figure>
    使用数学归纳法证明对于任意的$n\ge1$,一个$2^n\times2^n$的棋盘,如果去掉其中的一个正方形,那么剩下的部分可以被L型的Trominoes覆盖.

    本题要证明的命题$P(n)$是对于任意的$n\ge1$,一个$2^n\times2^n$的棋盘,如果去掉其中的一个正方形,那么剩下的部分可以被L型的Trominoes覆盖.

    对于基本步骤, 需要证明$P(1)$为真,将$P(n)$中的$n$替换为$1$,得到一个$2\times2$的棋盘,如果去掉其中的一个正方形,那么剩下的部分可以被L型的Trominoes覆盖.
    如左图所示

    显然,$P(1)$为真.

    接着,来看归纳步骤.假设$P(k), k\ge1$为真,即对于任意的$k\ge1$,一个$2^k\times2^k$的棋盘,如果去掉其中的一个正方形,那么剩下的部分可以被L型的Trominoes覆盖.
    我们需要证明$P(k+1)$为真,即对于任意的$k+1\ge1$,一个$2^{k+1}\times2^{k+1}$的棋盘,如果去掉其中的一个正方形,那么剩下的部分可以被L型的Trominoes覆盖.

    将一个$2^{k+1}\times2^{k+1}$的棋盘分成四个$2^k\times2^k$的子棋盘,去掉的那个正方形必然在其中的一个子棋盘中,根据归纳假设,这个子棋盘剩下的部分可以被L型的Trominoes覆盖.

    将其他三部分的缺口拼成一个L型的Trominoes,覆盖在四个子棋盘的交界处,如右图所示

    所以$P(k+1)$为真.$\blacksquare$

    <figure markdown="span">
    ![Trominoes-BaseCase](Chapter5%20Squence/images/base-case.webp){width="200" align=left}
    ![Trominoes-BaseCase](Chapter5%20Squence/images/inductive-step.webp){width="200" align=right}
    </figure>

5.3 强数学归纳法和良序性公理

强数学归纳法和良序性公理

强数学归纳法(strong mathematical induction) 与数学归纳法有一些类似,都包括基本步骤和归纳步骤,但强数学归纳法的归纳步骤不再是假设一个整数$k$满足$P(k)$为真,而是假设对于所有满足$a\le i\le k$的整数$i$,$P(i)$为真,然后利用这些假设来证明$P(k+1)$为真.

强数学归纳法原理指的是,如果满足以下两个条件

$P(a), P(a+1), \cdots, P(b)$都为真
对于任意整数$k\ge b$,如果对于所有满足$a\le i\le k$的整数$i$,$P(i)$为真,那么$P(k+1)$也为真

那么对于任意的整数$n\ge a$,$P(n)$为真.

假设$P(i), a\le i\le k$为真被称为推理假设(inductive hypothesis)

强数学归纳法有很多不同的名称，包括第二归纳法(second principle of induction),第二有限归纳法(the second principle of finite induction)和完全归纳法(the principle of complete induction)

强数学归纳法证明的例子

证明任意大于$1$的整数都可以被一个质数整除.

本题要证明的命题$P(n)$是 $$ n\text{可以被一个质数整除}, n>1 $$ 对于基本步骤, 需要证明$P(2)$为真,将$P(n)$中的$n$替换为$2$,得到 $$ 2\text{可以被一个质数整除} $$ 因为$2$是一个质数,所以$P(2)$为真.
接着,来看归纳步骤.假设整数$k\ge2, 2\le i\le k$的整数$i$,$P(i)$为真,即 $$ i\text{可以被一个质数整除} $$ 需要证明$P(k+1)$为真,即$k+1$可以被一个质数整除为真.
情况1:$k+1$是一个质数,那么$k+1$可以被一个质数整除(它自己),所以$P(k+1)$为真.
情况2:$k+1$不是一个质数,那么$k+1=ab$,其中$2\le a,b\le k$.根据推理假设,$P(a)$和$P(b)$都为真,即$a$和$b$都可以被一个质数整除.因此,$k+1$也可以被一个质数整除,即$P(k+1)$为真.$\blacksquare$

良序性公理

良序性公理(well-ordering principle)指的是,每一个非空的自然数集合都有一个最小元素.

良序性公理,数学归纳法以及强归纳法三者是完全等价的.

使用良序性公理证明强数学归纳法

设$P(n)$是一个关于整数$n\ge a$的命题,满足以下两个条件
1. $P(a), P(a+1), \cdots, P(b)$都为真

使用强数学归纳法证明数学归纳法

使用数学归纳法证明良序性公理