Finding the $n$th term of a particular sequence

I have a sequence on $\mathbb{N}\times\mathbb{N}$ whose $n$th term I wish to find out. In fact, any information regarding this sequence will be helpful. The sequence is denoted as $(x_1,y_1),(x_2,y_2),(x_3,y_3)\cdots$ and is constructed as follows:

1. Set $x_1=1$.
2. Given that $x_i$ has been constructed let $y_i=x_i+2i$.
3. Assuming $(x_i,y_i)$ has been constructed we define $x_{i+1}$ as follows: Consider the multiset $M$ of all the numbers of the type $x_j$ or $y_j$, with $1\le j\le i$. Let $m$ be the least odd number in $\mathbb{N}$ which has multiplicity at most $1$ in $M$. Define $x_{i+1}=m$.
4. Go to step 2.

Note that the difference of the two coordinates successively yields the even numbers, and all odd numbers are used exactly twice.

So the initial few terms are : $(1,3),(1,5),(3,9),(5,13),(7,17),(7,19),(9,23),(11,27),(11,29)\cdots$.

Any help will be appreciated.

-
This is an unusual way to build a sequence. What is its origin? –  vadim123 Oct 24 '13 at 1:48
@vadim123: I am trying to construct a specific mathematical design. The sequence is going to be used in that. –  Shahab Oct 24 '13 at 3:10
Probably of no use, but what if you consider the sequence $\bigl(\frac{x_i-1}2,\frac{y_i-1}2\bigr)_i$? Perhaps it has a more visible pattern. –  Matemáticos Chibchas Oct 27 '13 at 7:45

Earlier Answer without proof:

$x_n=2\lfloor \frac{n}{\sqrt{2}}-\frac{1}{2}\rfloor+1$ or equivalently $x_n=$ $n/\sqrt{2}$ rounded to nearest integer, doubled minus 1. $y_n=x_n+2n$.

I haven't been able to prove this despite speding quite some time.

The given sequence can be equivalently defined as: $x_1=1,x_2=1$ and for $n>1$ $x_{n+1} = \left\{\begin{array}{1} x_n+2\text{ if }x_n=x_{n-1}\text{ or }x_n=x_j+2j\text{ for some }j \in \mathbb{N}\\x_n \text{ otherwise}\end{array}\right.$

We use induction to show that $x_n=a_n\equiv2\lfloor \frac{n}{\sqrt{2}}-\frac{1}{2}\rfloor+1$. The initial conditions hold as $a_1=a_2=1=x_1=x_2$. Suppose $a_i=x_i$ for $i=1,...,n>1$. We will show that $a_{n+1}=x_{n+1}$. Define $f(x)=\frac{x}{\sqrt{2}}-\frac{1}{2}$ so $a_n=2\lfloor f(n) \rfloor+1$.

Let $f(n)=\frac{n}{\sqrt{2}}-\frac{1}{2}=k+r$ where $k\in \mathbb{N},0<r<1$. Note $a_n=2k+1$ and $r$ is irrational.

Consider $j=\lfloor \frac{n}{\sqrt{2}+1}+\frac{1}{2}\rfloor=\lfloor (\sqrt{2}-1)n+\frac{1}{2}\rfloor=\lfloor 2(\frac{1}{2}+k+r)-n+\frac{1}{2}\rfloor= 2k-n+1+\lfloor2r+\frac{1}{2}\rfloor$. Now we consider 4 exclusive and exhaustive cases.

Case 1: $0<r<\frac{1}{4}$.

We have $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$ so $a_{n-1}=2k-1=a_n-2$ and $k<f(n+1)=k+r+\frac{1}{\sqrt{2}}<k+\frac{1}{4}+\frac{1}{\sqrt{2}}<k+1$ so $a_{n+1}=2k+1=a_n$. Also, $j=2k-n+1$ so $f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\frac{1}{\sqrt{2}}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\frac{1}{\sqrt{2}}-\frac{1}{2}=n-k-1-r(\sqrt{2}+1)$.

Using $0<r<\frac{1}{4}$, $\lfloor f(j) \rfloor = n-k-2$ and $\lfloor f(j+1) \rfloor = \lfloor f(j)+\frac{1}{\sqrt{2}} \rfloor = n-k-1$. That is, $j+\lfloor f(j) \rfloor = k-1$ and $(j+1)+\lfloor f(j+1) \rfloor = k+1$. So $\not\exists i \in \mathbb{N}$ such that $i+\lfloor i \rfloor=k$ or equivalently $x_i+2i=x_n$. By definition, $x_{n+1}=x_n=a_n=a_{n+1}$.

Case 2: $\frac{1}{4}<r<1-\frac{1}{\sqrt{2}}$.

Again, we have $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$ so $a_{n-1}=2k-1=a_n-2$ and $k<f(n+1)=k+r+\frac{1}{\sqrt{2}}<k+1$ so $a_{n+1}=2k+1=a_n$. This time, $j=2k-n+2$ so $f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\sqrt{2}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\sqrt{2}-\frac{1}{2}=n-k-1+\frac{1}{\sqrt{2}}-r(\sqrt{2}+1)$.

Using $\frac{1}{4}<r<1-\frac{1}{\sqrt{2}}$, $\lfloor f(j) \rfloor = n-k-1$ and $\lfloor f(j-1) \rfloor = \lfloor f(j)-\frac{1}{\sqrt{2}} \rfloor = n-k-2$. That is, $j+\lfloor f(j) \rfloor = k+1$ and $(j-1)+\lfloor f(j-1) \rfloor = k-1$. So $\not\exists i \in \mathbb{N}$ such that $i+\lfloor i \rfloor=k$ or equivalently $x_i+2i=x_n$. By definition, $x_{n+1}=x_n=a_n=a_{n+1}$.

Case 3: $1-\frac{1}{\sqrt{2}}<r<\frac{1}{\sqrt{2}}$.

We have $k-1<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k$ so $a_{n-1}=2k-1=a_n-2$ and $k+1<k+r+\frac{1}{\sqrt{2}}=f(n+1)<k+2$ so $a_{n+1}=2k+3=a_n+2$. As in Case 2, $j=2k-n+2$ so $f(j)=\sqrt{2}k-\frac{n}{\sqrt{2}}+\sqrt{2}-\frac{1}{2}=(n-\frac{1}{\sqrt{2}}-r\sqrt{2})-(\frac{1}{2}+k+r)+\sqrt{2}-\frac{1}{2}=n-k-1+\frac{1}{\sqrt{2}}-r(\sqrt{2}+1)$.

Using $1-\frac{1}{\sqrt{2}}<r<\frac{1}{\sqrt{2}}$, $\lfloor f(j) \rfloor = n-k-2$ so $j+\lfloor f(j) \rfloor = k$ or equivalently $x_j+2j=x_n$. By definition, $x_{n+1}=x_n+2=a_n+2=a_{n+1}$.

Case 4: $\frac{1}{\sqrt{2}}<r<1$.

We have $k<k+r-\frac{1}{\sqrt{2}}=f(n-1)<k+1$ so $a_{n-1}=2k+1=a_n$ and $k+1<k+r+\frac{1}{\sqrt{2}}=f(n+1)<k+2$ so $a_{n+1}=2k+3=a_n+2$. Since, $x_n=a_n=a_{n-1}=x_{n-1}$, by definition, $x_{n+1}=x_n+2=a_n+2=a_{n+1}$.

-
Thanks. Could you tell me how you arrived at this expression initially? –  Shahab Oct 26 '13 at 10:18
Mostly guesswork. $x_{n+1}-x_n$ equals $0$ or $2$ and for large $N$, $(x_{N+1}-x_1)/N$ is approximately $\sqrt{2}$, generating values based on your algorithm. The formula I gave produces odd numbers that change by $0$ or $2$ and does not result in more than 2 repetitions of a value. The problem is showing that a certain value occurs $1$ or $2$ times exactly as it should according to your algorithm. That is, decimal part of $n/\sqrt{2}-0.5$ is between $1-1/\sqrt{2}$ and $1/\sqrt{2}$ precisely when there exists $j$ such that $\lfloor n/\sqrt{2}-0.5 \rfloor = \lfloor j/\sqrt{2}-0.5 \rfloor + j$. –  user96614 Oct 26 '13 at 15:12
I am unable to understand how your equivalent definition is a good definition. It does not seem to unambiguously define $x_{n+1}$. –  Shahab Nov 3 '13 at 7:22
@Shahab I am not sure why you consider the definition ambiguous. Does qualifying $j<n$ help? Note $x_n$ is a non-decreasing sequence so $x_n =x_j +2j$ is not possible for $j\ge n$. –  user96614 Nov 3 '13 at 10:21