MathLabs

第6問

関数 f(x,y)f(x,y) はすべての非負整数 x,yx,y に対して次を満たす。f(0,y)=y+1,f(0,y) = y+1, f(x+1,0)=f(x,1),f(x+1,0) = f(x,1), f(x+1,y+1)=f(x,f(x+1,y))f(x+1,y+1) = f\big(x, f(x+1,y)\big) f(4,1981)f(4,1981) を求めよ。
ステップ 4/7: x=3x=3 の段階を解く
前のステップ次のステップ
ざっくり言うと

再帰の各段階は、前の段階より1つ「上」の演算になる。加法は倍加になり、倍加はやがて累乗塔になる。

f(3,0)+3=8=23,f(3,y+1)+3=2(f(3,y)+3)  ⟹  f(3,y)+3=2 y+3f(3,0)+3=8=2^{3},\quad f(3,y+1)+3=2\big(f(3,y)+3\big) \implies f(3,y)+3=2^{\,y+3}
詳しい解説

規則 (2) とステップ3より、f(3,0)=f(2,1)=2(1)+3=5f(3,0)=f(2,1)=2(1)+3=5 なので、f(3,0)+3=8=23f(3,0)+3=8=2^3 である。規則 (3) とステップ3より、f(3,y+1)=f(2,f(3,y))=2f(3,y)+3f(3,y+1)=f(2,f(3,y))=2f(3,y)+3 だから、f(3,y+1)+3=2(f(3,y)+3)f(3,y+1)+3=2(f(3,y)+3)。8=238=2^3 から始まるこの倍加漸化式より、f(3,y)+3=2y+3f(3,y)+3=2^{y+3} を得る。