A sequence $(a_n)_{n=1}^{\infty}$ of positive integers satisfies the condition $a_{n+1} = a_n +\tau (n)$ for all positive integers $n$ where $\tau (n)$ is the number of positive integer divisors of $n$. Determine whether two consecutive terms of this sequence can be perfect squares.
Problem
Source: 2012 Balkan Shortlist BMO N1
Tags: number theory, Sequence, Perfect Squares, consecutive, Perfect Square
15.04.2020 08:06
06.08.2021 05:54
kvs wrote:
Its clearly wrong, how can u put $n = m^2$ ?
06.08.2021 06:08
MatBoy-123 wrote: kvs wrote:
Its clearly wrong, how can u put $n = m^2$ ? I guess he meant that $a_n=m^2$ where it is a perfect square then it is right.
06.08.2021 07:25
Sprites wrote: MatBoy-123 wrote: kvs wrote:
Its clearly wrong, how can u put $n = m^2$ ? I guess he meant that $a_n=m^2$ where it is a perfect square then it is right. No he is assuming that $n = m^2$ and $a_n = m^2$... i.e. $a_{m^2} = m^2$ which is not being proofed..
06.08.2021 07:41
No he meant that suppose that $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$
06.08.2021 08:03
Sprites wrote: No he meant that suppose that $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$ No, plz have a look at a question first, how he can put both $a_n$ and $n$ equals $m^2$
06.08.2021 08:16
MatBoy-123 wrote: Sprites wrote: No he meant that suppose that $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$ No, plz have a look at a question first, how he can put both $a_n$ and $n$ equals $m^2$ He didn't say that $n=m^2$,he said that for some arbitarty n $a_n=m^2$ I actually don't understand why you are confused,he never even wrote in his post that $n=m^2$,he wrote that $a_n=m^2$ He assumed that suppose that for some arbitarty n(which may or may not be a perfect square) $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$ Hence no two consecutive terms of this sequence are perfect squares @above,yeah I hadn't read his post correctly :sorry:
06.08.2021 08:37
Sprites wrote: MatBoy-123 wrote: Sprites wrote: No he meant that suppose that $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$ No, plz have a look at a question first, how he can put both $a_n$ and $n$ equals $m^2$ He didn't say that $n=m^2$,he said that for some arbitarty n $a_n=m^2$ I actually don't understand why you are confused,he never even wrote in his post that $n=m^2$,he wrote that $a_n=m^2$ He assumed that suppose that for some arbitarty n(which may or may not be a perfect square) $a_n=m^2$ then $a_{n+1}=m^2+\tau(m^2)$ which cant be a square since $m^2<m^2+\tau(m^2)<(m+1)^2$ Hence no two consecutive terms of this sequence are perfect squares Question is $a_{n+1} = a_n +\tau (n)$ , and you are understanding it $a_{n+1} = a_n +\tau (a_n)$
06.08.2021 09:17
Assume $a_n$ and $a_{n+1}$ are both perfect squares. This implies that $\tau(n)=a_{n+1}-a_n\geq 2\sqrt{a_n}+1$. It is well known that $\tau(n)\leq 2\sqrt{n}+1$. Furthermore we know that $a_n=a_1+\tau(1)+...+\tau(n)=a_1+\lfloor\frac{n}{1}\rfloor+\cdots +\lfloor\frac{n}{n}\rfloor$ Therefore we must have $2\sqrt{n}+1\geq \tau(n+1)\geq 2\sqrt{a_n}+1\geq 2\sqrt{1+\lfloor\frac{n}{1}\rfloor+\cdots +\lfloor\frac{n}{n}\rfloor}+1\implies n+1\geq\lfloor\frac{n}{1}\rfloor+\cdots +\lfloor\frac{n}{n}\rfloor$ but for all $n>2$ this is a contradiction since $\lfloor\frac{n}{1}\rfloor+\cdots +\lfloor\frac{n}{n}\rfloor>\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{n}=n+1$. The only case left to check is $n=1,2$;for $n=1$ we have $a_2=a_1+1$ but they could only be perfect squares if $a_1=0$ but it is impossible since they must all be positive, integers; for $n=2$ we have $a_3=a_2+2$ but this can't happen.
06.08.2021 10:14
@above you made a typo, it is \(\tau(n)=a_{n+1}-a_{n}\), but your argument is still valid, just change \(n+1\) to \(n\) in your inequality and it works fine, my solution is essentially the same too.
25.04.2023 14:56
We will use two well-know facts about $\tau(n)$ $$\tau(n) \le 2 \sqrt n + 1$$$$\tau(n)=\sum_{k=1}^{m} (\lfloor \frac{m}{k} \rfloor - \lfloor \frac{m-1}{k} \rfloor) \qquad$$ Assume $a_n$ and $a_{n+1}$ are both perfect squares. Then $\tau(n) \ge 2 \sqrt a_n +1$. Thus $$2 \sqrt n + 1 \ge 2 \sqrt a_n +1 \iff n \ge a_n \iff n \ge a_1 + \sum_{k=1}^{n-1} \tau(k) \iff n \ge a_1 + \sum_{k=1}^{n-1} \lfloor \frac{n-1}{k} \rfloor$$ So if $n \ge 3 \implies n \ge a_1+n$ which is not true. Checking $n=1$ and $n=2$ also yields there is not such squares $\blacksquare$
04.02.2024 18:25
It is well-known that $\tau(n)\le 2\sqrt{n}+1$ and $$\tau(1)+\tau(2)+\dots+\tau(n)=\left\lfloor \frac{n}{1}\right\rfloor+\left\lfloor \frac{n}{2}\right\rfloor+\dots+\left\lfloor \frac{n}{n}\right\rfloor.$$Also, notice that $$a_{n+1}=a_1+\tau(1)+\tau(2)+\dots+\tau(n)=a_1+\left\lfloor \frac{n}{1}\right\rfloor+\left\lfloor \frac{n}{2}\right\rfloor+\dots+\left\lfloor \frac{n}{n}\right\rfloor.$$ Suppose that $a_n$ and $a_{n+1}$ are perfect squares, i.e. $a_n=m^2$ and $a_{n+1}=k^2$, where $k\ge m+1$. Therefore, $$2\sqrt{n}+1\ge\tau(n)=a_{n+1}-a_n=k^2-m^2\ge 2m+1.$$Hence, $$\sqrt{n}\ge m \iff n \ge a_n=a_1+\left\lfloor \frac{n-1}{1}\right\rfloor+\left\lfloor \frac{n-1}{2}\right\rfloor+\dots+\left\lfloor \frac{n-1}{n-1}\right\rfloor.$$Now if $n=1$ or $n=2$, we easily obtain a contradiction. If $n\ge 3$, we get $$n=a_1+\left\lfloor \frac{n}{1}\right\rfloor+\left\lfloor \frac{n}{2}\right\rfloor+\dots+\left\lfloor \frac{n}{n}\right\rfloor\ge a_1+(n-1) + 1 = a_1+n,$$which is impossible. Therefore, two consecutive terms of the sequence cannot be perfect squares.
19.11.2024 17:03
Here's a quick solution. Note that the sequence is strictly increasing, in particular $a_n \geq n$ for all $n$. Now if $a_n = m^2$, then $a_{n+1}$ to be a square requires $a_{n+1} \geq (m+1)^2$, thus \[ 2m+1 \leq a_{n+1} - a_n = \tau(n) \leq 2\sqrt{n} \leq 2\sqrt{a_n} = 2m\]contradiction.