翻了一下SICP才找到比较简略的证明:证明如下:
设存在数对序列(ak,bk)//k是脚码,其中ak>bk,假设欧几里得算法在第k步结束。
首先证明一个基础定理:若(ak+1,bk+1),(ak,bk),(ak-1,bk-1)是规约数列中连续的三个数对,那么必有bk+1≥bk+bk-1。//再次声明,式中出现的k,k-1,k+1都是脚码
假设上述定理成立,由算法可知,b≥1,那么当k(算法结束所需步骤)为一时结论成立,因为此时Fib(1)=1
接下来假设所有小于k的整数都成立,那么设法建立对k+1的结果。
令(ak+1,bk+1),(ak,bk),(ak-1,bk-1)是归约数对连续三个数对,我们有 bk≥Fib(k)和bk-1≥Fib(k-1),这样,应用已证明的定理和Fibonacci的定义,可以给出bk+1≥bk+bk-1≥Fib(k+1),这就完成了拉密定理的证明