Let $f:\mathbb{N}\to\mathbb{N}$ be defined in the following recursive way: for any $n$ in $\mathbb{N}$, $f(n)$ is the least natural number different from all $f(k)$ and $f(k)+k+1$ with $k<n$ (for instance, $f(0)=0$, $f(1)=2$, $f(2)=3$, $f(3)=5$). Is it possible to define this function in the language of Presburger arithmetic (the same question about the function defined as above, but with $f(k)+k$ instead of $f(k)+k+1$)?

1$\begingroup$ If we call $g$ the second function you defined then $g(k+1)=f(k)+1$ for all $k$. So $g$ is definable in Presburger arithmetic if and only if $f$ is. $\endgroup$ – Ramiro de la Vega Nov 21 '12 at 14:32

1$\begingroup$ The first 20 values of $f(n)$ match oeis.org/A022342 , which has the growth rate $n(1+\sqrt 5)/2+O(1)$, and hence is not definable in Presburger arithmetic. $\endgroup$ – Emil Jeřábek Nov 21 '12 at 15:07

$\begingroup$ Not only the first 20 values of $f(n)$ match the corresponding ones at oeis.org/A022342  all values given there are the same as the corresponding function values. A proof of the general statement is thus desirable. $\endgroup$ – Dimiter Skordev Nov 21 '12 at 19:10
$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in http://oeis.org/A022342: $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{1}\rfloor=\lfloor(n+1)\fii\rfloor1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.
Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $nF_i$. This is known as the Zeckendorf expansion of $n$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\ol a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.
Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.
Since $F_i=\bigl(\fii^i(\fii)^{i}\bigr)/\sqrt5$, we have $$f(n)\fii n=\sum_{i:a_i=1}(F_{i+1}\fii F_i)=\sum_{i:a_i=1}(\fii)^{i}\frac{\fii^{1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(\fii)^{i}.$$ Thus, \begin{align*} f(n)\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{i}=\frac{\fii^{2}}{1\fii^{2}}=\fii^{1},\\\\ f(n)\fii n&>\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{i}=\frac{\fii^{3}}{1\fii^{2}}=\fii^{2}=\fii^{1}1, \end{align*} which shows $(*)$.
Suppose, toward a contradiction, that $f$ is definable in Presburger arithmetic. By quantifier elimination for Presburger arithmetic, there must be a constant $M$ such that, on each congruence class modulo $M$, $f$ is an affine function $f(n)=an+b$ except for finitely many $n$'s, and the coefficient $a$ of the linear term is rational. Furthermore, since $f$ is clearly monotone, these coefficients $a$ must be the same for all of the congruence classes.
Now consider (approximately) what happens when we compute, using the inductive definition, $f(n)$ for a large $n$, large enough so that the constant terms $b$ are negligible. $f(n)$ is defined as the first number different from the $n$ numbers $f(k)$ and the $n$ other numbers $f(k)+k+1$ for all $k$ in the range $0\leq k<n$. Notice first that "other" is literally correct; no number appears in both sets of $n$. How many of these $2n$ numbers are relevant in the sense that they are below $f(n)$ and thus really matter in the calculation of $f(n)$? One answer to this question is $f(n)$, since $f(n)$ is the first number above all of them; remember that this is roughly $an$. Another answer is that all of the first set of $n$ (the values of previous $f(k)$'s) are relevant, but in the second set, whose largest elements are roughly $an+n$, only those below roughly $an$ are relevant. Altogether, we have roughly $n+(an/(an+n))=n(2a+1)/(a+1)$ relevant numbers, and $f(n)$, being the first number different from these, is roughly of this size. Thus, we must have $a=(2a+1)/(a+1)$. This means that $a$ must equal the golden ratio. But we know, from quantifier elimination, that $a$ must be rational. This contradiction shows that $f$ cannot be definable in Presburger arithmetic.

$\begingroup$ The argument I gave for the growth rate, approximately linear with the golden ratio as coefficient, was done under the assumption of Presburger definability, an assumption that I showed is false. Nevertheless, the growth rate looks plausible even without the false assumption, and its plausibility is certainly increased by Emil's comment (which arrived while I was typing my answer). $\endgroup$ – Andreas Blass Nov 21 '12 at 15:17

$\begingroup$ Let $\alpha=\liminf_nf(n)/n$, $\beta=\limsup_nf(n)/n$. Clearly $1\le\alpha\le\beta\le2$, and I believe your argument gives $\beta\le1+\beta/(1+\alpha)$ and $\alpha\ge1+\alpha/(1+\beta)$. This implies $1+\beta\le\alpha\beta\le1+\alpha$, thus $\alpha=\beta=\phi$, i.e., $f(n)\sim\phi n$. $\endgroup$ – Emil Jeřábek Nov 21 '12 at 20:13