什么是数学归纳法?
数学归纳法的思想是 有限到无限 的递推逻辑,证明某个命题对其所有定义范围均成立,其本质是:
- 基例:证明命题在初始条件 n=base 下成立。
- 归纳假设:假设某个命题在 n=k 的时候成立。
- 归纳步骤:证明某个命题在 n=k+1 的时候也成立。
若上述条件均满足则说明命题对 n≥base 的在定义域内的自然数且均成立。
在某些特殊情况下,如当前状态可能依赖于多个前置状态,在归纳假设时需要假设 n≤k 均成立,此方法被称为强归纳法。
例题
用数归证明斐波那契数列通项公式
命题:斐波那契数列满足 F(n)=ϕn–ψn√5,其中 ϕ=1+√52(黄金比例),ψ=1−√52。
证明:
-
基例
- 当 n=0 时,F(0)=0,代入上式成立。
- 当 n=1 时,F(1)=1,代入上式成立。
-
归纳假设
由于 F(n) 依赖于多个前驱,故需要使用强归纳法。
- 归纳假设所有 k≤n,F(k)=ϕk–ψk√5 均成立。
-
归纳步骤
-
根据递推公式 F(n+1)=F(n)+F(n–1) 可得:
F(n+1)=ϕn–ψn√5+ϕn−1–ψn−1√5=ϕn+ϕn−1–(ψn+ψn−1)√5. -
由于 ϕ 和 ψ 方程 x2=x+1 的两个解,所以我们可以得到:
ϕn+1=ϕn+ϕn−1, ψn+1=ψn+ψn−1. -
带入可得:
F(n+1)=ϕn+1–ψn+1√5.
证毕
-