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) を求めよ。
ステップ 1/7: x=1x=1 の段階を解く：基底と漸化
前のステップ次のステップ
ざっくり言うと

x=1x=1 では、再帰は 22 から始めて「1を繰り返し加える」だけになる。

f(1,0)=f(0,1)=2,f(1,y+1)=f(0,f(1,y))=f(1,y)+1f(1,0)=f(0,1)=2,\quad f(1,y+1)=f(0,f(1,y))=f(1,y)+1
詳しい解説

規則 (2) を x=0x=0 で用いると規則 (1) より f(1,0)=f(0,1)=1+1=2f(1,0)=f(0,1)=1+1=2 が得られる。規則 (3) を x=0x=0 で用いると再び規則 (1) より f(1,y+1)=f(0,f(1,y))=f(1,y)+1f(1,y+1)=f(0,f(1,y))=f(1,y)+1 が得られ、f(1,⋅)f(1,\cdot) は各段階でちょうど 11 ずつ増加する。