I want to prove the following version of the Recursion Theorem
Let $S$ be a nonempty set and let $S^{*}=\bigcup_{n=1}^{\infty}S^{n}$. Let $s\in S$ and let $f:S^{*}\rightarrow S$ be a function. Then there exists a unique function $\varphi:\mathbb{N}\rightarrow S$ such that $\varphi\left(1\right)=s$ and $$\varphi\left(n+1\right)=f\left(\left(\varphi\left(1\right),\ldots,\varphi\left(n\right)\right)\right)$$ for all $n\in\mathbb{N}$.
I have already proven the more primitive version of the Recursion Theorem, the one that allows us to define a function whose value at a natural number $n>1$ is based on its value at $n-1$. This will be used in the proof.
The proof, which is based on Dasgupta goes as follows:
First, let us introduce some notation. Let $n\in\mathbb{N}$, let $x=\left(x_{1},\ldots,x_{n}\right)$ be an $n$-tuple of elements of $S$, and let $t\in S$. We define $x\ast t=\left(x_{1},\ldots,x_{n},t\right)$. Define a function $g:S^{*}\rightarrow S^{*}$ by $g\left(x\right)=x\ast f\left(x\right)$ for all $x\in S^{*}$. Then by the primitive Recursion Theorem, there exists a unique function $\phi:\mathbb{N}\rightarrow S^{*}$ such that $\phi\left(1\right)=\left(s\right)$ and $\phi\left(n+1\right)=g\left(\phi\left(n\right)\right)$ for all $n\in\mathbb{N}$. A simple argument using the Principle of Induction shows that $\phi\left(n\right)\in S^{n}$ for all $n\in\mathbb{N}$. Now define a function $\varphi:\mathbb{N}\rightarrow S$ as follows. If $n\in\mathbb{N}$, then $\varphi\left(n\right)$ is defined to be the $n$th coordinate of $\phi\left(n\right)$.
Dasgupta then goes on to claim that $\varphi$ is the required function. I am having trouble showing that $$\varphi\left(n+1\right)=f\left(\left(\varphi\left(1\right),\ldots,\varphi\left(n\right)\right)\right)$$ for all $n\in\mathbb{N}$.
Obviously, induction is the way to go, but I've tried and couldn't prove it.
Notice that $\phi(1)=(\varphi(1))$, $\phi(2)=\phi(1)*f(\phi(1))=(\varphi(1),f(\varphi(1)))=(\varphi(1),\varphi(2))$ etc. We will prove by induction that $\phi(n)=(\varphi(1),\varphi(2),\dots,\varphi(n))$. This is straightforward since, by induction, $$\phi(n+1)=g(\phi(n))=\phi(n)*f(\phi(n))=\bigl(\varphi(1),\varphi(2),\dots,\varphi(n),f(\phi(n))\bigr)=(\varphi(1),\varphi(2),\dots,\varphi(n+1)),$$ where the last equality follows by definition. Hence, we have $\varphi(n+1)=f(\phi(n))=f(\varphi(1),\dots,\varphi(n))$.