Define a sequence $\langle f(n)\rangle^{\infty}_{n=1}$ of positive integers by $f(1) = 1$ and \[f(n) = \begin{cases} f(n-1) - n & \text{ if } f(n-1) > n;\\ f(n-1) + n & \text{ if } f(n-1) \leq n, \end{cases}\]for $n \geq 2.$ Let $S = \{n \in \mathbb{N} \;\mid\; f(n) = 1993\}.$ (i) Prove that $S$ is an infinite set. (ii) Find the least positive integer in $S.$ (iii) If all the elements of $S$ are written in ascending order as \[ n_1 < n_2 < n_3 < \ldots , \]show that \[ \lim_{i\rightarrow\infty} \frac{n_{i+1}}{n_i} = 3. \]
Problem
Source: IMO Shortlist 1993, India 1
Tags: limit, algebra, Sequence, recurrence relation, IMO Shortlist
Vor
26.06.2006 13:33
i think it is very easy.I have $f(3)=6$ and if $f(n)=2n$ then $f(3n-1)=2(3n-1)$
Rust
26.06.2006 17:26
Let $m_1=3,m_{k+1}=3m_k-1$, then first mean when $f(n_1)=a>0$ is $3m_l-1-2a$, were l is first suth that $m_l>a$. In this case (a=1993) $n_1=12417$. All terms satisfyed recurent equation $n_{k+1}=3n_k+4a-1$. Therefore $n_k=3^{k-1}n_1+(3^{k-1}-1)\frac{4a-1}{2}=\frac{5*3^{k+7}-7971}{2}$.
Math-wiz
23.09.2019 20:36
Umm.... I have a doubt I am trying to prove the first part. Suppose $f(n-1)\leq n$. Then, $f(n)=f(n-1)+n$, which will be greater than $n$. Thus, $f(n+1)=f(n)-n=f(n-1)$. Hence, the sequence is periodic with period 2. But, this is not happening here. What is the mistake?
InkretBear
23.09.2019 23:10
It is greater than $n$ but not necessarily greater than $n+1$.
rchokler
24.09.2019 01:32
$f(n)$ is OEIS A046901 It is a concatenation $S_0,S_1,S_2,S_3,\cdots$ where $S_n$ is the sequence $b_0,b_1,\cdots,b_{k-1}$ for $k=5\cdot 3^n$ where $b_0=1$, $b_{2j}=k+j$, and $b_{2j+1}=\frac{k+1}{2}-j$ In each block $S_n$ with $n\geq 7$, we have $b_{5\cdot 3^n-3984}=1993$. So for $n\geq 7$ we have $f\left(\frac{3(5\cdot 3^n-2657)}{2}\right)=1993$.
Math-wiz
24.09.2019 06:31
InkretBear wrote: It is greater than $n$ but not necessarily greater than $n+1$. Oops! Right. Thanks Inkretbear