a sequence $(a_n)_{n\ge0}$ is defined by $a_0=1$ and $$a_{n+1}=a_{{\lfloor}\frac{7n} {9}{\rfloor}}+a_{{\lfloor}\frac{n}{9}{\rfloor}}$$ for $n\ge0$.prove that there is an $n$ such that $a_n<\frac{n}{2001!}$
how do i approach this? we see that $a_1=2,a_3=a_4=3,a_5=a_6=a_7=4,a_8=a_9=5$.Is there any pattern coming out?Does induction work here?
On
The following is inspired by
where the similar problem
Set $a_0 = 1$ and for $n \ge 1$, $a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor}$. Find $\lim_{n\to\infty} a_n/n$.
is solved (also mentioned in this answer).
The idea is to prove that the sequence satisfies $$ \tag{$*$} a_n \le C n^r $$ for all $n \ge 1$, with some suitably chosen $r \in (0, 1)$ and some $C > 0$. First, the exponent $r$ is chosen such that $$ \left( \frac{7}{9}\right)^r + \left( \frac{1}{9}\right)^r < 1 \, , $$ for example $\boxed{r = 0.8}$. Next, the factor $C$ is chosen $(*)$ holds for $1 \le n \le 9$, for example $\boxed{C = 2}$. Finally, $(*)$ is proven for all $n \ge 1$ with induction.
It follows from $(*)$ that $$ \lim_{n \to \infty} \frac{a_n}{n} = 0 \, , $$ so that $a_n / n < 1/2001!$ eventually.
Proof by contradiction
Assume: $$\forall n\exists a_n\ge\frac{n}{2001!}$$ Consider: $$a_{2001!}\ge\frac{2001!}{2001!}=1$$ now using the recurrance relation: $$a_{2001!+9}=a_{\left\lfloor\frac{7(2001!+9)}{9}\right\rfloor}+a_{\left\lfloor\frac{2001!+9}{9}\right\rfloor}$$ $$a_{2001!+9}=a_{\left\lfloor\frac{7\times2001!}{9}+\frac{7\times9}{9}\right\rfloor}+a_{\left\lfloor\frac{2001!}{9}+\frac99\right\rfloor}$$ Now notice that $\frac{7\times2001!}{9}\in\mathbb{Z}$ and $\frac{7\times9}{9}=7$ so the first term's floor bracket contains an integer. Similarly, $\left(\frac{2001!}{9}+1\right)\in\mathbb{Z}$. As a result $a_{2001!+9}\ge1+1=2$. Repeating this for any $a_{2001!+9k}$ where $k\in\mathbb{Z^+}$ yields the same inequality. This implies: $\forall n>2001!,a_n\ge2$.
Now, comparing $a_{2\times2001!}\ge2$ to $\frac{2\times2001!}{2001!}=2$ shows a contradiction as we assumed: $$a_n\ge\frac{n}{2001!}\forall n$$ But we have shown that: $$a_{2\times2001!}<\frac{2\times2001!}{2001!}=2$$ Hence our initial assumption must be false: $$\therefore\exists n\,\,s.t.\,\,a_n<\frac{n}{2001!}$$ And that completes the proof
EDIT:
Let $b_n = \frac{a_n}{n}$.
Consider $b_{2001!}$. By the recurrence relation: $$b_{2001!} = \frac{a_{2001!}}{2001!} \geq \frac{1}{2001!}$$ Now, let's compute $b_{2001! + 9}$: $$b_{2001! + 9} = \frac{a_{2001! + 9}}{2001! + 9}$$ Notice that $b_{2001! + 9}$ depends only on $b_n$ for $n$ in the range $[2001!, 2001!+9]$. Since there are 10 terms in this range, by the Pigeonhole Principle, at least one of these terms must be less than or equal to the average: $\frac{b_{2001!} + b_{2001! + 1} + \ldots + b_{2001! + 9}}{10}$ Therefore, there exists $k$ such that $b_{2001! + k} \leq \frac{b_{2001!} + b_{2001! + 1} + \ldots + b_{2001! + 9}}{10}$. Since $b_{2001!} \geq \frac{1}{2001!}$, we have: $\frac{b_{2001!} + b_{2001! + 1} + \ldots + b_{2001! + 9}}{10} \geq \frac{1}{2001!}$ Combining the above inequalities, we get: $b_{2001! + k} \leq \frac{1}{2001!}$ This implies: $a_{2001! + k} \leq \frac{2001! + k}{2001!} = 1 + \frac{k}{2001!}$ Finally, since $k \geq 0$, we have: $a_{2001! + k} < 1 + \frac{1}{2001!} \leq \frac{1}{2001!}$ This completes the proof, demonstrating that there exists an $n$ (specifically, $n = 2001! + k$) such that $a_n < \frac{n}{2001!}$.