I'm studying Algorithms and Computability course and I've encountered a proof that I cannot finish. It comes from the Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science book by Martin Davis, Ron Sigal, Elaine J. Weyuker (page 63). The only solution to this problem I found online is paywalled. It looks as follows:
Prove that $ f_{i} $ defined in the following way:
$ f(0, y) = g_{1}(y) $
$ f(x + 1, 0) = g_{2}(x) $
$ f(x + 1, y + 1) = h(x, y, f(x, y + 1), f(x + 1, y)) $
where $g_{1}$, $g_{2}$, $h$, are primitive recursive, is primitive recursive.
The idea presented during the classes was that this function represents a diagonal on a x, y axis. Because the recursive functions provided are unusual, we have started with the encoding:
We define $ F(k) = \Pi^{k+1}(f(0,k), f(1,k-1),...,f(k,0)) $ where $\Pi^{k+1}$ is an encoding function (it doesn't matter which encoding we'll use in this case). This $F(k)$ represents the k-th diagonal encoding. This encoding function is primitive recursive and decodes k+1 element.
Next, the decoding function: $f(x,y) = \sigma_{x+1}^{x+y+1}F(x+y)$ where $\sigma_{x+1}^{x+y+1}$ is a decoding function that is primitive recursive. It decodes x+1-th element from the set of x+y+1 elements.
Hence: $\Pi^{x+y+1}=(f(0,x+y), f(1,x+y-1),...,f(x+y, 0))$
Coming to the actual proof. We'll use the primitive recursive schema.
$F(0) = \Pi^{1}(f(0,0))=$ const value, so this step holds
$F(k+1)=\Pi^{k+2}(f(0,k+1),f(1,k),...,f(k,1),f(k+1,0))$
From the task we know that we can replace some elements inside the encoding function - mainly the first and the last element, because $f(0,k+1)=g_{1}(k+1)$ and $f(k+1,0)=g_{2}(k)$. But I'm stuck here. How does the end of the proof look like? What to do with the elements in the middle? I will be very thankful for the answer!