每日一题[173]数学归纳法

无锡市2015年春学期普通高中期末考试高二理科数学压轴题:

将\(1\)到\(n\)的\(n\)个正整数按下面的方法排成一个排列,要求:除左边的第一个数外,每个数都与它左边(未必相邻)的某个数相差\(1\),将此种排列称为“\(n\)排列”.比如“\(2\)排列”为当\(n=2\)时,有\(1,2\);\(2,1\);共\(2\)种排列.“\(3\)排列”为当\(n=3\)时,有 \(1,2,3\);\(2,1,3\);\(2,3,1\);\(3,2,1\);共\(4\)种排列.

(1)请写出“\(4\)排列”的排列数;

(2)问所有“\(n\)排列”的结尾数只能是什么数?请加以证明;

(3)证明:“\(n\)排列”共有\(2^{n-1}\)个.


cover(1)  \(1,2,3,4\),\(2,1,3,4\),\(2,3,1,4\),\(3,2,1,4\),\(2,3,4,1\),\(3,2,4,1\),\(3,4,2,1\),\(4,3,2,1\).

(2)解及证明  “\(n\)排列”的结尾数只能是\(1\)和\(n\).

首先证明以下引理:

引理  任何“\(n+1\)排列”中去掉数\(n+1\)后的\(n\)个数一定组成“\(n\)排列”.

若“\(n+1\)排列”中\(n+1\)排在\(n\)的右边,那么去掉这个数对其他所有数都没有影响,因此组成“\(n\)排列”;

若“\(n+1\)排列”中\(n+1\)排在\(n\)的左边,那么\(n+1\)只可能排在左边第一位,此时去掉这个数对其他所有数都没有影响,因此组成“\(n\)排列”.

根据引理,任何一个“\(n+1\)排列”都必然由某个“\(n\)排列”通过在适当的位置添加\(n+1\)得到.接下来用数学归纳法证明命题.

归纳基础显然成立.

假设“任何\(n\)排列”的结尾是\(1\)或\(n\),那么对于“\(n+1\)”排列,只有两种可能:

方式一  当“\(n\)排列”以\(n\)结尾时,直接在结尾添加\(n+1\),此时符合题意;

方式二  当“\(n\)排列”以\(1\)结尾时,或者直接在结尾添加\(n+1\),或者将\(n+1\)添加在非结尾的位置,此时“\(n+1\)排列”以\(1\)结尾,符合题意.

因此命题得证.

(3)证明  用数学归纳法证明.

归纳基础显然成立.

假设“\(n\)排列”共有\(2^{n-1}\)个,那么考虑“\(n+1\)排列”可以通过两种方法得到:

方式一  直接在“\(n\)排列”结尾添加\(n+1\),因此以\(n+1\)结尾的“\(n+1\)排列”有\(2^{n-1}\)个;

方式二  “\(n\)排列”的每个数都增加\(1\),然后在结尾添加\(1\),因此以\(1\)结尾的“\(n+1\)排列”有\(2^{n-1}\)个.

因此命题得证.


  引理的证明非常重要,这是数学归纳法得以递推的关键步骤.

此条目发表在每日一题分类目录,贴了, 标签。将固定链接加入收藏夹。

每日一题[173]数学归纳法》有2条回应

  1. fly说:

    第三问不太严谨,没有说明这种构造无漏网之鱼

发表回复