递推 从幂集合说起

1、2自然数有无穷个自然数有无穷个天下无人都数过天下无人都数过人说小毛会数数人说小毛会数数不知他能数几多不知他能数几多序序 曲曲 递推法起源于自然数计数递推法起源于自然数计数. 一个小孩从一个小孩从1数到了数到了1万，你还不能承认他已经会数数了万，你还不能承认他已经会数数了. 递推递推 从从1 1开始开始 依次加依次加1 1因为自然数是无穷的因为自然数是无穷的. 怎样才能承认他已经数会了无穷的怎样才能承认他已经数会了无穷的自然数呢？检查的办法就是自然数呢？检查的办法就是“递推法递推法”：（2）然后由你随便说一个自然数）然后由你随便说一个自然数 n ，问他：后面的一个，问他：后面的一个数是多少数是多

2、少. 如果他回答说是如果他回答说是n+1.此时，你得承认他数会了无穷的自然数此时，你得承认他数会了无穷的自然数.（1）先让他说出一个具体的数，比如）先让他说出一个具体的数，比如1；4一一 由由2到到3 递推法起步递推法起步二二 由由1到到n 两分法启蒙两分法启蒙三三 数学归纳法数学归纳法 由由k到到k+1四四 幂集合与幂数列幂集合与幂数列目目 录录【问题】【问题】 高中数学第一章第一例：高中数学第一章第一例： 写出集合写出集合a，b的所有子集的所有子集.【解析】【解析】 由子集的定义和集合的列举法，可以写由子集的定义和集合的列举法，可以写出出a，b的所有子集如下的所有子集如下 ，a， b， a

3、，b【说明】【说明】 它们也形成了一个集合：它们也形成了一个集合： a， b， a，b，称其为集合，称其为集合a，b的子的子集集合集集合集合集合a，b的幂集合的幂集合.【讨论】【讨论】 按集合元素的无序性，子集集合按集合元素的无序性，子集集合 ，a， b， a，b 的写法共有的写法共有4！=24种种.如如 a， ，b， a，b 就是其中的就是其中的一种写法一种写法.试问：我们在写试问：我们在写a,b的子集集合时，你是习惯于前者，还是的子集集合时，你是习惯于前者，还是后者？后者？显然，这两个写法有很大的区别：前者在无序的理论中进行显然，这两个写法有很大的区别：前者在无序的理论中进行着有序的操作着

4、有序的操作按元素由少到多排序，而后者把无序的理按元素由少到多排序，而后者把无序的理论当成了无序的操作论当成了无序的操作子集列队没有任何规矩子集列队没有任何规矩.【问题】【问题】 写出集合写出集合a,b,c的所有子集的所有子集.【解析】【解析】 先拿来集合先拿来集合a,b的所有子集，排成左下方的三角阵的所有子集，排成左下方的三角阵在后一个三角阵的每个集合中，依次添上第三个元素在后一个三角阵的每个集合中，依次添上第三个元素c，则得一个，则得一个新的三角阵新的三角阵. 这两个三角阵中这两个三角阵中“元素元素”的集合，便是的集合，便是a,b,c所有子所有子集（的集合）集（的集合）.ccc a, ba，

5、b a, b ， a，b， 将左边的三角阵复制成另一个相同三角阵（如右）将左边的三角阵复制成另一个相同三角阵（如右）【思考】【思考】 这是一个关于这是一个关于“3”的问题，考虑拿的问题，考虑拿“2”递推递推. 递推递推法原理：法原理：3=2+1 这个这个1就是就是1个元素个元素. a,b, ca,b, a,c, b,ca,b,c将新的三角阵将新的三角阵“下移下移”一行，与原三角阵错位相一行，与原三角阵错位相并，即得并，即得H3=a,b,c的三阶子集三角阵：的三阶子集三角阵：依次递推，我们还可以得到依次递推，我们还可以得到H4=a,b,c,d的四阶三角阵的四阶三角阵加法原理：加法原理：4=3+1

6、 这个这个1就是第就是第4个元素小个元素小d . a, ,b, , c, a,b, , a,c, , b,c, a,b,c, d dd dd dd dd dd dd dd d a,b, c，a,b, a,c, b,c，a,b,c，将新的三角阵将新的三角阵“下移下移”一行，与原三角阵一行，与原三角阵“错位错位”相并，即得相并，即得H4=a,b,c,d 的四阶子集三角阵：的四阶子集三角阵：a, b, c , d d a, b,d ,a,c,d , b,c,d a, d ,b,d , c,d 这就是四元集合这就是四元集合H4=a, b, c , d 的三角阵，杨辉三角的三角阵，杨辉三角形就从这儿起源

7、形就从这儿起源.说说 明明由由2到到3、由、由3到到4的问题解决之后，的问题解决之后，我们已经领会到我们已经领会到 “递推法递推法”的本意：的本意：由由1开始，由任何已知的开始，由任何已知的k，都能把，都能把它推向它推向k+1. 因此，由因此，由1到到n的问题也的问题也可以由递推解决可以由递推解决. 划分，到底将事物分成几类？在子集划分，到底将事物分成几类？在子集扩展的递推过程中给出了扩展的递推过程中给出了“两分法两分法”. .分类思想、分类法，是分析事物的基本思分类思想、分类法，是分析事物的基本思想方法，由此产生了想方法，由此产生了“划分法划分法”. .两分法的重要性，在于这种方法把事两分法

8、的重要性，在于这种方法把事物分成物分成“互补互补”的两部分：从整体到的两部分：从整体到部分是一分为二，从部分到整体是合部分是一分为二，从部分到整体是合二而一二而一. . 问题问题 集合集合H1=x1的子集有的子集有a1=21个，个，H2=x1,x2的子集有的子集有a2=22个个.试求集合试求集合Hn=x1,x2,xn的子集个数的子集个数an.思考思考 按两分法，这个数列按两分法，这个数列an是个是个以以2为首项，以为首项，以2为公比的等比数列为公比的等比数列. 如果补上如果补上n=0，则数列成为一个以，则数列成为一个以1为首为首项，以项，以2为公比的等比数列为公比的等比数列. 这个数列也称这个

9、数列也称幂数列，其重要性与等差数列中的自然数幂数列，其重要性与等差数列中的自然数列相对应列相对应.a1=21,a2=22,a3=23,猜想猜想an=2n，假设假设Hk=x1,x2,xk -1，xk的子集有的子集有ak=2k个个.则可摆成如下的则可摆成如下的k阶子集三角阵：阶子集三角阵：两分法解析【解析续】【解析续】 在原三角阵的每个子集中，依次添在原三角阵的每个子集中，依次添入第入第k+1个元素，得一新的个元素，得一新的k阶三角阵阶三角阵.显然，新显然，新三角阵的子集个数也为三角阵的子集个数也为ak=2k.xk+1x1，xk+1,x2,xk+1，xk , xk+1x1 ， x2，xk +1，x

10、1, x3, xk+1，xk -1,xk, xk+1x1 ， x2 ， ，xk，xk +1新新由加法原理，由加法原理，Hk+1=x1, x2，xk， xk+1的子集个数为的子集个数为2k+2k =2k+1，这实际上是在用数归纳法证明幂数列，这实际上是在用数归纳法证明幂数列2n的通项公式的通项公式an=2n. 理论依据就是两分法理论依据就是两分法.数数学归纳法学归纳法 由由k到到k+1数学归纳法，是自然数计数的发展数学归纳法，是自然数计数的发展.自然数计数用的是递推法（自然数计数用的是递推法（1）从）从1开始；（开始；（2）依次加）依次加1.所以，自然数计数就是所以，自然数计数就是“起起1加加1

11、法法”. 这里的这里的“起起”讲的是讲的是有一个开头，不是有一个开头，不是1，而是任一个已知的自然数，而是任一个已知的自然数 k 也行；也行；“加加”的意思是紧跟，即明确的意思是紧跟，即明确 k 后面紧跟的那一个数是后面紧跟的那一个数是 k +1.数学归纳法也是这两步：数学归纳法也是这两步：第一步：第一步：n=1（或（或 k ）时，论证结论正确，这就是开头；）时，论证结论正确，这就是开头；第二步：当认定第二步：当认定 n = k 结论正确时，论证结论正确时，论证 n = k+1时结论也时结论也正确，这就是紧跟正确，这就是紧跟.由此看到，数学归纳法与自然数计数的道理相同，都是由此看到，数学归纳法

12、与自然数计数的道理相同，都是“起起1加加1”的思想方法的思想方法.数数学归纳法学归纳法 由由k到到k+1幂集合元素个数计数公式的探索幂集合元素个数计数公式的探索 an= 2n【观察】【观察】 x1的子集有的子集有a 1=2=21 个，个， x1，x2 的子集有的子集有a2=4=22 个；个； x1，x2，x3 的子集有的子集有a 3 =8=23 个；个； .于是，我们有如下的猜想于是，我们有如下的猜想.【猜想】【猜想】 集合集合 x1，x2，x3 ，xn 的子集有的子集有a n = 2n 个个【分析】【分析】 这是一个关于这是一个关于“自然数计数问题自然数计数问题”的证明，可以考的证明，可以考

13、虑虑“起起1加加1”的递推法原理，并发展其为数学归纳法的证明：的递推法原理，并发展其为数学归纳法的证明：（1）检验）检验 n =1时，结论真；时，结论真；（2）当）当 n = k 结论真时，论证结论真时，论证 n =k+1时结论也真时结论也真.数数学归纳法学归纳法 由由k到到k+1【求证】【求证】 集合集合 x1，x2，x3 ，xn 的子集有的子集有a n = 2n 个个【证明】【证明】 n=1时，集合为时，集合为x1，它的子集有，它的子集有a1=21，结论真，结论真.假设假设n = k 时结论真，即集合时结论真，即集合Hk = x1，x2，xk 的子集有的子集有a k=2k 个个. 在在 H

14、k 中再加上第中再加上第 xk+1个元素，则成为集合个元素，则成为集合 H k+1= x1，x2，xk ，xk+1，它的子集由两部分组成，它的子集由两部分组成.第一部分，不含第一部分，不含xk+1的子集的子集,即即 Hk 的所有子集，由假设，的所有子集，由假设，a k=2k第二部分，含第二部分，含xk+1的子集，即在的子集，即在Hk每个子集中添上元素每个子集中添上元素 xk+1而得，而得，也有也有ak =2k 个个. 由加法原理，由加法原理，Hk+1 的子集有的子集有 ak+1=2k +2k =2 k+1因此，集合因此，集合 Hn = x1，x2，x3 ，xn 的子集有的子集有a n = 2n

15、 个个数数学归纳法学归纳法 由由k到到k+1【求证】【求证】 集合集合 Hn = x1，x2，x3 ，xn 的子集有的子集有a n = 2n 个个【证明】【证明】 集合集合 Hn 子集的形成过程分子集的形成过程分 n 步步.第一步，对于第一步，对于 x1，有取和舍两种可能；，有取和舍两种可能；第二步，对于第二步，对于 x2，有取和舍两种可能；，有取和舍两种可能；第第 n 步，对于步，对于xn，有取和舍两种可能，有取和舍两种可能.由乘法原理，由乘法原理，Hn子集的形成方法有子集的形成方法有 222=2n 种种因此，集合因此，集合 Hn = x1，x2，x3 ，xn 的子集有的子集有a n = 2

16、n 个个用乘法原理证明公式用乘法原理证明公式 an =2n 幂集合与幂数列幂集合与幂数列集合集合 Hn = x1，x2 ，xn 的子集也形成一个集合，这个集的子集也形成一个集合，这个集合称作合称作 Hn 幂集合，是因为幂集合，是因为Hn 的子集个数正好形成幂数列的子集个数正好形成幂数列 a n = 2n 当当 n= 0时，集合时，集合Hn为空集，子集只为空集，子集只1个，即个，即a 0=20=1.幂集合得名于数列幂集合得名于数列 an =2n 当当 n为正整数时，集合为正整数时，集合Hn为非空集合，子集个数是一个以为非空集合，子集个数是一个以2为首为首项，以项，以2为公比的等比数列为公比的等比

17、数列. 取取 n N，幂数列，幂数列 an 的前的前7项依次如下表项依次如下表n01234562n1248163264编号1234567幂集合与幂数列幂集合与幂数列第第 n 个自然数是个自然数是 n -1问问:第第1个自然数是什么？答个自然数是什么？答:是是0；问问:第第2个自然数是什么？答个自然数是什么？答:是是1;问：第问：第100个自然数是什么？答：是个自然数是什么？答：是99按以上问答，第按以上问答，第n个自然是个自然是 n-1.这点和正整数不同：第这点和正整数不同：第1个正整数是个正整数是1，第，第2个正整数是个正整数是2，第第 n 个正整数是个正整数是n. 即正整数即正整数 n 就是它的序号数就是它的序号数 n . 而自然数却而自然数却是它的序号数减是它的序号数减1. 为了使得幂数列与幂集合对应，我们通常将幂数列写成如下形式为了使得幂数列与幂集合对应，我们通常将幂数列写成如下形式 an = 2n -1其中其中n为自然数为自然数n-1的序号数，于是有的序号数，于是有 a1 = 1 ，a 2 = 2，a3 = 4，幂集合与幂数列幂集合与幂数列公式公式 an+1 = Sn +1幂数列的通项公式记作幂数列的通项公式记作