関数が終了する証明

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の形式の整数を考えて誘導を使う」というヒントがあります。ヒントがなければ、むしろ難しい質問です。

したがって、ヒントを使用して、いくつかのiとkに対して任意の数値を(2i+1)2^k - 1と書くことができます。 kは、基底2の数字の最後にある1の数であることがわかります。

これを使用すると、Fが誘導によって終了することを証明することができます。k。 (2i+1)2^0 - 1が偶数であるため、k = 0の基底は即時です。

そうでない場合、k> 0の場合、(2i+1)2^k - 1は奇数です。それは小さなkを持っている、と我々は終わったので、次に、帰納法の仮定により、

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)は終了します。