以题主 @inversioner 的数学水平,想来对这个问题是没什么困难的
不过既然问了这个问题,并且提到初等方法,我就写一个让绝大部分中学生也能看懂的证法吧,正好这个初等证法我最早也是在中学时自学线性代数时搞出来的
其实关于k阶齐次线性常系数递推数列的通项公式的证法,虽然有不少种,但本质上就两大类
其中一大类,就是把初等证法线性代数化,用代数的语言,引入矩阵、行列式、位移算子、差分算子,来重新描述证明过程
比如周义仓、曹慧、肖燕妮《差分方程及其应用》中,就记载了用位移算子和差分算子的方法证明过程
而陈泽安、韩创新、黄楚清、高泽红《递推数列》中,写了用矩阵和线性代数方法证明的过程
另一大类证明法,就是利用母函数或者z变换,将原本的离散的数列问题,转化为连续的函数的问题
这方面的证明,我记得
许胤龙、孙淑玲《组合数学引论》
潘永亮、徐俊明《组合数学》
等组合数学教材中有详细记录,我就不多赘述了
我曾在斐波那契数列通项推导过程的问题下,将我写的初等证法写了一遍:
实际上这里的关键就是
递推数列:
其中 , 是常数,
如果它的特征方程
它的 个特征根 无重根
那么它的任意一个特征根 ( )
的 次方
是递推式:
的一个特解
我想,最早给出初等证明的前辈,应该和我当时一样,也是发现这一点,受等比数列启发,才找到这步构造方法
当然这里就不可避免的涉及到一些线性代数的思想
比如对于齐次线性递推数列,在不考虑初值的情况下,它的几个解的线性组合仍然是它的解
这样才能保证最后给出通解
另外,像 这样的特解,其实就是解空间的基底
最后,证明通解形式的唯一性,还是不可避免得用到线性代数中的范德蒙德行列式
我那个回答主要是为了回答斐波那契数列的问题,因此就没有写含有重根的情况,在这儿简单补充一下
假设特征方程
它有 个互不相同的特征根
它们的代数重数分别为
满足 ( )
并且
那么这个递推数列:
的通解将会是这样的形式:
其中 ( , )是任意常数
这里的关键是证明
如果特征方程
它的任意一个特征根 ( )的代数重数为
则
全都是递推式:
的特解
这个结论的证明需要用到线性代数中的一个定理:
但是很显然,这个定理的证明非常简单,是普通中学生都能轻易看明白的
运用这个引理一代入,结论是很显然的
最后同样要证明,这 个特解构成的通解形式是唯一的,同样也是像无重根的情况下一样,用线性方程组的系数矩阵的行列式不为0来证明,这里的系数矩阵的行列式是广义范德蒙德行列式
(证明略)
定义移位运算 ,其作用于数列 得到 使得 则数列 满足递推公式 即 。
设多项式 各 不同,则由 互素,存在多项式 使得 从而 (逐项求和)
其中 满足 。
而 其中 为常数
这是由于 进而 以此类推,得到 其中 简记为 即得。
所以 即为结论。