Let \(d(n)\) denote the number of positive divisors of \(n\). The sequence \(a_0\), \(a_1\), \(a_2\), \(\ldots\) is defined as follows: \(a_0=1\), and for all integers \(n\ge1\), \[a_n=d(a_{n-1})+d(d(a_{n-2}))+\cdots+ {\underbrace{d(d(\ldots d(a_0)\ldots))}_{n\text{ times}}}.\]Show that for all integers \(n\ge1\), we have \(a_n\le3n\). Proposed by Karthik Vedula
Problem
Source: ELMO Shortlist 2023 N4
Tags: Elmo, number theory
IAmTheHazard
30.06.2023 03:00
If you're willing to do some bashing I think this is a non-problem, but I haven't done the details: Use $d(N) \leq 2\sqrt{N}$ It takes about $\log \log N$ applications of $d$ to make $N$ go to $2$ for $N>1$ (the specific value is easy to find) Prove that this is, say, at most $\sqrt[4]{N}$ for $N$ larger than some fairly small value, probably using calculus. Thus everything but the first $\sqrt[4]{N}$ terms in the summation are at most $2$ By inductive hypothesis $d(a_{n-1})$ is at most $2\sqrt{3n}$ and $d^2(a_{n-2})$ through $d^{\sqrt[4]{n}}(a_{n-\sqrt[4]{n}})$ is at most $\sqrt[4]{12n}$ Add everything together and get a polynomial inequality (in $\sqrt[4]{n}$) we want to prove, which should be true for $n$ larger than some fairly small value Write out everything less than that
rama1728
30.06.2023 05:55
IAmTheHazard wrote: If you're willing to do some bashing I think this is a non-problem, but I haven't done the details: Use $d(N) \leq 2\sqrt{N}$ It takes about $\log \log N$ applications of $d$ to make $N$ go to $2$ for $N>1$ (the specific value is easy to find) Prove that this is, say, at most $\sqrt[4]{N}$ for $N$ larger than some fairly small value, probably using calculus. Thus everything but the first $\sqrt[4]{N}$ terms in the summation are at most $2$ By inductive hypothesis $d(a_{n-1})$ is at most $2\sqrt{3n}$ and $d^2(a_{n-2})$ through $d^{\sqrt[4]{n}}(a_{n-\sqrt[4]{n}})$ is at most $\sqrt[4]{12n}$ Add everything together and get a polynomial inequality (in $\sqrt[4]{n}$) we want to prove, which should be true for $n$ larger than some fairly small value Write out everything less than that Another thing you can do is to make use of the fact that $d(n)\leq 2\sqrt{n}-1$ for \(n>8\) and get that \(a_n\leq d(a_{n-1})+2(\sqrt{d(a_{n-2})} + \sqrt{d(d(a_{n-3}))} + \cdots) -n+1\) and then we can use cauchy schwarz, as well as utilize the fact that the sum of the terms inside the square roots is just \(a_{n-1}\), and then finish it off through a clean inductio
sman96
30.06.2023 13:06
Clearly, $d(n) \leq \frac n2 + 1$. So we get, \begin{align*}
d^k(n)&\leq \frac{n}{2^k}+ \frac1{2^{k-1}}+\dots + \frac12+1 \\
& < \frac n{2^k} + 2\\
\implies d^k(n) &\leq \left\lfloor\frac n{2^k} + 2\right\rfloor = \left\lfloor\frac n{2^k} \right\rfloor + 2\qquad(1)
\end{align*}Here, $$a_n = \sum\limits_{k=1}^nd^k(a_{n-k}) \qquad(2)$$Now, we apply induction, assume that $a_m \leq 3m \ \ \forall m < n$.
Now, for $k > \frac n 3$ in $(2)$, \begin{align*}
d^k(a_{n-k}) &\leq \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor + 2\\
&\leq \left\lfloor\frac {3(n-\frac n 3)}{2^{\frac n 3}} \right\rfloor + 2 \\
&\leq \left\lfloor\frac {2n}{2^{\frac n 3}} \right\rfloor + 2
\end{align*}
Now, we can easily show that if $n \geq 16 $ then $\left\lfloor\frac {2n}{2^{\frac n 3}} \right\rfloor = 0$.
So, we compute the base cases for $n < 16$. And then in $(2)$ all the terms with $k > \frac n 3$ will be at most $2$.
Now, \begin{align*}
a_n &= \sum\limits_{k=1}^nd^k(a_{n-k}) \\
&\leq \sum\limits_{k=1}^n \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor + 2\\
&= 2n+ \sum\limits_{k=1}^n \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor\\
&\leq 2n+ \sum\limits_{k=1}^{\lfloor n/3\rfloor} \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor+\sum\limits_{k=\lfloor n/3\rfloor+1}^{n} \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor\\
&=2n+ \sum\limits_{k=1}^{\lfloor n/3\rfloor} \left\lfloor\frac {a_{n-k}}{2^k} \right\rfloor\\
& \leq 2n+ \sum\limits_{k=1}^{\lfloor n/3\rfloor} \frac {a_{n-k}}{2^k}\\
& \leq 2n+ \sum\limits_{k=1}^{\lfloor n/3\rfloor} \frac {3(n-k)}{2^k} < 2n+ \sum\limits_{k=1}^{\lfloor n/3\rfloor} \frac {3n}{2^k} < 2n + n = 3n \ \ \blacksquare
\end{align*}
amirhsz
27.12.2023 11:25
Warning: This solution is purely written for the precision, probably no one will write it on the exam. Lol Quote: Claim1: $\forall n\neq 12: d(n)\le \sqrt{\frac{8n}{3}}$
Proof: assume that $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{k}^{\alpha_{k}}$ and $n\neq 12$ then we have to prove: $\frac{d(n)}{\sqrt{n}}\le\sqrt{\frac{8}{3}}$
and we have: $\frac{d(n)}{\sqrt{n}}=\prod_{i=1}^{k}\frac{\alpha_{i}+1}{p_{i}^{\frac{\alpha_{i}}{2}}}$
$\bullet $ if $p_{i}>3$ then we can see that: $\frac{\alpha_{i}+1}{p_{i}^{\frac{\alpha_{i}}{2}}}\le \frac{\alpha_{i}+1}{5^\frac{\alpha_{i}}{2}}\le\frac{2}{\sqrt{5}}$ (you can easily prove the last Inequality by induction on $\alpha_{i}$)
$\bullet $if $p_{i}=3$ we have two cases:$\begin{cases}
\alpha_{i}=1: \frac{\alpha_{i}+1}{p_{i}^\frac{\alpha_{i}}{2}}=\frac{2}{\sqrt{3}}\\\\
\alpha_{i}>1: \frac{\alpha_{i}+1}{p_{i}^\frac{\alpha_{i}}{2}}\le 1 \text{(you can prove it by induction, again)}
\end{cases}$
$\bullet $if $p_{i}=2$ we have two cases:$\begin{cases}
\alpha_{i}=2: \frac{\alpha_{i}+1}{p_{i}^\frac{\alpha_{i}}{2}}=\frac{3}{2}\\\\
\alpha_{i}\neq2: \frac{\alpha_{i}+1}{p_{i}^\frac{\alpha_{i}}{2}}\le \sqrt{2} \text{(you can prove it by induction, again)}
\end{cases}$
now it's clear if $n\neq12$ we have $d(n)\le \sqrt{\frac{8n}{3}}$ (just combine cases)
now we are going to induction on n. you can check the problem for $n\le15$, now assume that problem is true for all $k<n$. we will prove it for $k=n$. Use this variable change to simplify: $x_{n-1}=a_{n-1}\\ x_{n-2}=d(a_{n-2})\\ \cdots \\ x_{0}=\underbrace{d(d(\ldots d(a_0)\ldots))}_{n-1\text{ times}}$ we can translate problems to these variables: $a_{n}=d(x_{n-1})+\cdots +d(x_{1})+d(x_{0})\\ x_{n-1}=x_{n-2}+\cdots +x_{1}+x_{0}$ now we just need a bound for 12's in sequence $x_{i}$. assume that k of $x_{i}$'s are equal to 12!. for example if $x_{i}=12$then we have: $12=x_{i}=\underbrace{d(d(\ldots d(a_{i})\ldots))}_{n-1-i\text{ times}}<\underbrace{2\sqrt{2\sqrt{\cdots \sqrt{2\sqrt{a_{i}}}}}}_{n-1-i\text{ times}}=2^{\sum_{j=0}^{n-i-2}2^{-j}}.a_{i}^{2^{-(n-i-1)}}<4.a_{i}^\frac{1}{2^{n-i-1}}\Longrightarrow \\ 3^{2^{n-i-1}} <a_{i}\le3i<3n\text{ logarithm}\Longrightarrow 2^{n-i-2}<( 2^{n-i-1}-1)log(3)< log(n)\text{ logarithm}\Longrightarrow \\ n-i-2< (n-i-2)log(2)< log(log(n))\Longrightarrow i\ge n-1-log(log(n))$ (I just used well known inequality: $d(n)>2\sqrt{n}$) now from the above inequality we can assume that $k\le log(log(n))+1$. for simplify we use another variable to show difference of: $s=d(12)-\sqrt{\frac{8.12}{3}}=6-\sqrt{32}$ now we can just use claim 1 and prove inequality for n: $a_{n}=d(x_{n-1})+\cdots +d(x_{1})+d(x_{0})< \sqrt{\frac{8}{3}}(\sum_{i=0}^{n-1}\sqrt{x_{i}})+s.k\\ \text{by Cauchy-Schwarz inequality: }\sum_{i=0}^{n-2}\sqrt{x_{i}}\le \sqrt{\sum_{i=0}^{n-2}x_{i}}.\sqrt{n-1}=\sqrt{x_{n-1}}.\sqrt{n-1}\\\Longrightarrow a_{n}<\sqrt{\frac{8}{3}}.\sqrt{x_{n-1}}.(\sqrt{n-1}+1)+s.k<\sqrt{8}\sqrt{(n-1)}.(\sqrt{n-1}+1)+s.log(log(n))$ now if we show the last term is less than $3n$, we win . $3n>?\sqrt{8}.\sqrt{n-1}(\sqrt{n-1}+1)+s.log(log(n))\\ \Longleftrightarrow \\ n(3-s.\frac{log(log(n))}{n})>n(3-(6-\sqrt{32})\frac{log(log(16))}{16})>n(3-\frac{1}{16})>?\sqrt{8}.\sqrt{n-1}.(\sqrt{n-1}+1)\text{ (I)}\\\Longleftrightarrow \\ n^2(3-\frac{1}{16})^2>?8(n-1)(n+2\sqrt{n-1})\\\Longleftrightarrow \\\frac{41}{10}x^4-16x^3+16x+1>?0, x\ge 4\Rightarrow \frac{41}{10}x^4>16x^3\text{ (II)}$ Remark1: in $(I)$ we used that $\frac{log(log(n))}{n}$ is a decreasing function and we already assume that $n>16$ Remark2: in $(II)$ I defined a new variable: $x=\sqrt{n}$ and we used $n>16$. Remark3:numbers in last inequalities are absolutely fake I'm sorry if there are grammar faults or typo. I know that wasn't a clean(it was really dirty) solution but I hope to be accurate:)