每日一题[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}$个．

（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}$个．

因此命题得证．

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