1.15

设 f:N→Nf:\mathbb{N} \rightarrow \mathbb{N} 满足 f(0)=1, f(0) = 1,

f(1)=4, f(1) = 4,

f(2)=6, f(2)=6,

f(x+3)=f(x)+(f(x+1))2+(f(x+2))3, f(x+3) = f(x)+(f(x+1))^2+(f(x+2))^3,

证明：f(x)∈PRFf(x) \in \mathcal{PRF}。

证明

令 g(x)=⟨f(x),f(x+1),f(x+2)⟩,f(x)=(g(x))1g(x) = \langle f(x), f(x+1), f(x+2) \rangle, f(x) = (g(x))_1

g(0)=⟨1,4,6⟩g(0) = \langle 1, 4, 6 \rangle，

g(x+1)=⟨(g(x))2,(g(x))3,(g(x))1+(g(x))22+(g(x))33⟩=B(g(x))g(x+1) = \langle (g(x))_2, (g(x))_3, (g(x))_1+(g(x))_2^2+(g(x))_3^3 \rangle = B(g(x))

这里，B(z)=⟨(z)2,(z)3,(z)1+((z)2)2+((z)3)3⟩∈PRFB(z) = \langle (z)_2, (z)_3, (z)_1+((z)_2)^2+((z)_3)^3 \rangle \in \mathcal{PRF}

故 g∈PRFg \in \mathcal{PRF}，从而 f∈PRFf \in \mathcal{PRF}。