See that $\lceil\phi\rceil=2=a_1$. We prove by induction that $a_n=\lceil n\phi\rceil$. We have:
$$a_n=a_{n-1}+1+f(n),$$where
$$f(n)=\begin{cases}1\text{ if }n=a_i\text{ for some }i;\\0\text{ if else.}\end{cases}$$It's easy to see that, if $a_i=n\implies i\leq n-1$. From the recurrence we have:
$$a_n=n+1+\sum_{2\leq k\leq n}f(k)=n+1+g(n)$$See that $g(n)$ is the amount of elements from $\{2,3,\dots,n\}$ which are in the sequence. Now, suppose that $a_k=\lceil k\phi\rceil$ for $k=1,2,\dots,n-1$. We have:
$$a_k\leq n\iff k\phi\leq n\iff k\leq\left\lfloor\frac{n}{\phi}\right\rfloor\implies g(n)=\left\lfloor\frac{n}{\phi}\right\rfloor.$$From this we conclude that:
$$a_n=n+1+\left\lfloor\frac{n}{\phi}\right\rfloor=n+\left\lceil\frac{n}{\phi}\right\rceil=\left\lceil n\left(1+\frac{1}{\phi}\right)\right\rceil=$$$$=\lceil n\phi\rceil,$$as desired. $\blacksquare$