Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal. (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.)
Problem
Source: Iran second round 2011
Tags: induction, number theory proposed, number theory
28.04.2011 18:39
I know that the answer is $a_n=n$ but I am having trouble to prove this statement.
28.04.2011 18:47
is it strictly increasing or just non-decreasing?
28.04.2011 18:57
goodar2006 wrote: (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.) I think you get your answer from this.
28.04.2011 19:06
First It`s easy to show the sequence is strictly increasing . Then use the fact that $d(n)$ is odd only for perfect squares $n$ . (There is an easier way to finish the problem , but it worths to thinking about it yourself )
28.04.2011 20:54
after proving that the sequence is strictly increasing, looking at $a_{2^{p-2}}$ where $p$ is a prime number can also solve the problem.
28.04.2011 20:57
goodar2006 wrote: after proving that the sequence is strictly increasing, looking at $a_{2^{p-2}}$ where $p$ is a prime number can also solve the problem. This is exactly what I wrote in my post , an easier way !
30.04.2011 21:22
Try to solve the generalization of this problem.
04.05.2011 19:44
as an intresting result; mahanmath proved that the problem statement is still true if we omit the increasing condition! you can think on it!
04.05.2011 20:58
Can someone finish the proof of this problem with induction? I solved this using induction but I don't remember how did I finish it...
04.05.2011 21:10
amparvardi wrote: Can someone finish the proof of this problem with induction? I solved this using induction but I don't remember how did I finish it... Could you write the start of your solution , (because my solution has an inductive progressing ,so It may help us to recovery (!!) your solution .)
04.05.2011 21:17
The only thing I remember is that I proved that $a_1=1, a_2=2,a_3=3$, which is not hard (just find the numbers for which $d(n)=2$, $d(n)=3$, and $d(n)=4$. Then you can easily find $a_1,a_2,a_3$). Then use (a stronger version of?) Bertrand's postulate (but I don't remember how to finish this part) and the problem will be solved really easy (but, the increasing condition helps when you're trying to use Bertrand's postulate).
04.05.2011 21:22
amparvardi wrote: The only thing I remember is that I proved that $a_1=1, a_2=2,a_3=3$, which is not hard (just find the numbers for which $d(n)=2$, $d(n)=3$, and $d(n)=4$. Then you can easily find $a_1,a_2,a_3$). Then use (a stronger version of?) Bertrand's postulate (but I don't remember how to finish this part) and the problem will be solved really easy (but, the increasing condition helps when you're trying to use Bertrand's postulate).
04.05.2011 21:29
mahanmath wrote:
- Then please post your solution with Bertrand's postulate, I am interested in seeing how to finish it. Thanks. Any attempts on the generalization of the problem? there should be a nice solution for this problem.
08.06.2019 18:14
goodar2006 wrote: Find all increasing sequences $a_1,a_2,a_3,...$ of natural numbers such that for each $i,j\in \mathbb N$, number of the divisors of $i+j$ and $a_i+a_j$ is equal. (an increasing sequence is a sequence that if $i\le j$, then $a_i\le a_j$.) I think I have a solution, but I'm not sure if my solution is correct.
28.01.2020 12:13
Solution without Bertrand's Postulate