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
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
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
30.06.2023 13:06
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}}$
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:)