函数终止的证明

Question

if x is even , then F(x)=x/2 else F(x) = F(F(3x+1))。证明了F(x)终止于所有整数x。

有人能帮我吗。我正在学习“计算机算法的基本原理”。我不知道该怎么做。

Answer 1

书中有一个提示您省略了：“考虑表单的整数(2i+1)2^k-1并使用归纳”。没有暗示，这是一个相当困难的问题。

因此，使用这个提示，请注意，您可以将任何数字写成(2i+1)2^k - 1来表示某些i和k。您可以观察到，k是基数2中数字底部的1s数。

使用此方法，您可以证明F在k上通过归纳终止。k=0的基本情况是即时的，因为(2i+1)2^0 - 1是偶数。

否则，当k>0，(2i+1)2^k - 1是奇数。然后

  F((2i+1)2^k - 1)
= F(F(3((2i+1)2^k - 1)+1))
= F(F(3(2i+1)2^k-2))
= F((3(2i+1)2^k-2)/2) (since k>0)
= F(((6i+3)2^k-2)/2)
= F((2(3i+1)+1)2^{k-1}-1)

根据归纳假设，F((2(3i+1)+1)2^{k-1}-1)终止，因为它有一个较小的k，我们就完成了。