Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 5 down vote accepted
+100

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.

Added Proof:

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}$.

share|improve this answer
    
Thanks. Could you tell me how you arrived at this expression initially? –  Shahab Oct 26 '13 at 10:18
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.