等差数列与固定点

等差数列与固定点

等差数列必须在公差为0，也就是等比为1的时候才算有固定点，或者就是伪等比数列a(n)=p*a(n-1)+q形式的。

目前差分导数来证明复杂度，并与采用固定点的方法做一个比较。

a(n)=p*a(n-1)+q

a(n-1)=p*a(n-2)+q

Go

a(n)-a(n-1)-p*{ a(n-1)-a(n-2) } =0

Go

x*x-x-p*(x-1)=0

Go

(x-p)*(x-1)=0

设通解为A*p^n+B

所以有如下方程组成立:

A+B=a(0)

A*p+B=p*a(0)+q

Go

A={(p-1)*a(0)+q}/(p-1)

B=a(0)-A=-q/(p-1)

 

下面看采用固定点的解法过程：

设a(n)-M=p*{a(n-1)-M}

得到a(n)的解为:

a(n)={a(0)-M}*p^n+M

加入初始条件有如下方程组：

{a(0)-M}*p^0+M=a(0)

{a(0)-M}*p^1+M=a(1)=p*a(0)+q

Go

a(0)*p-p*M+M=p*a(0)+q

Go

M=q/(1-p)

Go

通解为

{a(0)-M}*p^n+M={a(0)-q/(1-p)}*p^n+q/(1-p)=A*p^n+B

故得到证明。