PE440

一些证明,推荐复制入atom观看

首先我们考虑这个T(n)是什么,我们可以列出递归式:

(definition:T)

	T(0) = 1

	T(1) = 10

	T(n) = 10*T(n-1) + T(n-2)

这个数列与Fibonacci数列有着类似的性质,我们考虑如何计算它某两项的gcd.对于Fibonacci数列我们有:

[此下为Fibonacci数列的性质,关系不大]{

	(definition:F)

		F(0) = 0

		F(1) = 1

		F(n) = F(n-1) + F(n-2)

	(property:F)

	1.	F(x) Coprime F(x+1)

	2.	F(n) Divides F(k*n)

	3.	gcd(F(x),F(y)) = F(gcd(x,y))

	我们来证明一下这些性质,首先是 [1.] 证明:辗转相除显然

	这时我们可以发现,只要能证明 [3.] ,就可以推出 [2.] ,具体方法:

	(proof:[2.])

		假设命题 [3.] 为真:

		gcd(F(x),F(k*x))=F(gcd(x,k*x))=F(x)->[2.]

	我们考虑如何证明[3.], 我们发现有命题[4.]

	(property:F)

	4.	F(a+b)=F(a)*F(b+1)+F(a-1)*F(b)

	(proof:[4.])

		考虑对b归纳,

		basecase:

			F(a+0)=F(a)

			F(a+1)=F(a)+F(a-1)

		assume forall 0<=b<=t is true, extend to b+1:

			F(a+b  )=F(a)*F(b+1)+F(a-1)*F(b)

			F(a+b-1)=F(a)*F(b  )+F(a-1)*F(b-1)

			F(a+b+1)=F(a)*F(b+2)+F(a-1)*F(b+1) -> 符合命题

	(proof:[3.])

		gcd(F(a),F(a+t))=

		gcd(F(a),F(a)*F(t+1)+F(a+1)*F(t))=

		gcd(F(a),F(a+1)*F(t))=

		gcd(F(a),F(t))

		应用辗转相减法可得原命题

}

我们现在可以寻找这个T(n)的性质了,仿照寻找F(n)的性质(具体在上面),首先我们要找到T(n)关于很大的T(n+m)的关系.设

(equation:T1)

	T(n+m)=T(n)*A(m)+T(n-1)*B(m)

考虑待定系数法

(derivation:T1)

	T(n  )=T(n)

		A(0)=1

		B(0)=0

	T(n+1)=T(n)*A(1)+T(n-1)*B(1)

		A(1)=10

		B(1)=1

	T(n+m+1)=

	T(n+m)*10+T(n+m-1)=

	T(n)*A(m)*10+T(n-1)*B(m)*10+T(n)*A(m-1)+T(n-1)*B(m-1)=

	T(n)*(A(m)*10+A(m-1))+T(n-1)*(B(m)*10+B(m-1))

		A(m+1)=A(m)*10+A(m-1)

		B(m+1)=B(m)*10+B(m-1)

		<implies that>

		A(m)=T(m)

		B(m)=T(m-1)

	<reduce to>

	T(n+m)=T(n)*T(m)+T(n-1)*T(m-1)

(equation:B1)

	B(n+m)=T(n+m-1)=T(n)*T(m-1)+T(n-1)*T(m-2)=B(n+1)*B(m)+B(n)*B(m-1)

于是发现了与F(n)完全相同的形式,直接沿用F(n)的证明即可推出gcd(B(x),B(y))=B(gcd(x,y))也即gcd(T(n),T(m))=T(gcd(n+1,m+1)-1)

那么剩下的就是求gcd(c^a+1,c^b+1)(b>a), 我们可以考虑gcd(c^b-c^a,c^b+1)., c^b-c^a = c^(b-a)*(c^(b-a)-1) 显然 c^(b-a) Coprime c^b+1,

gcd(c^a+1,c^b+1)=gcd(c^b-c^a,c^a+1)=gcd(c^|b-2a|-1,c^a+1) 然后就变成了一个类似辗转相减的东西(我还是不很会整个分析),但是打个表就可以知道这东西值是

c^gcd(a,b)+1 a/gcd(a,b),b/gcd(a,b) odd otherwise

2 c even otherwise

1 c odd

然后这道题就做完了吧