N 6

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

N 6

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 4 Y

Y by narutomath96, UpvoteFarm, Adventure10, Mango247

Let $\{a_{n}\}$ be a strictly increasing positive integers sequence such that $\gcd(a_{i}, a_{j})=1$ and $a_{i+2}-a_{i+1}>a_{i+1}-a_{i}$ . Show that the infinite series $\sum^{\infty}_{i=1}\frac{1}{a_{i}}$ converges.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

352 posts

ali666

#2 h Jun 17, 2008, 8:46 PM • 5 Y

Y by narutomath96, Adventure10, UpvoteFarm, Mango247, and 1 other user

maybe the problem is not exatly same writen here...because the condition $\gcd(a_i,a_j) = 1$ is extra...
$a_n - a_{n - 1} > a_{n - 1} - a_{n - 2} > .... > a_2 - a_1\geq1$ therefore $a_n - a_{n - 1}\geq{n - 1}$ ...and also:

$a_k = (a_k - a_{k - 1}) + (a_{k - 1} - a_{k - 2}) + .... + (a_2 - a_1) + a_1\geq{(k - 1) + (k - 2) + .... + 1 + 1}\Rightarrow{a_k > \frac {k(k - 1)}{2}} \\ \Longrightarrow\sum^{\infty}_{i = 1}\frac {1}{a_{i}} < \frac {1}{a_1} + \sum^{\infty}_{i = 2}\frac {2}{i(i - 1)} = a_1 + 2\sum^{\infty}_{i = 2}{\frac {1}{i - 1} - \frac {1}{i}} = a_1 + 2$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#3 h Jun 17, 2008, 10:16 PM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

Very good point, and nice solution. I have no idea what $\gcd(a_i,a_j)=1$ is doing there.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#4 h Jun 17, 2008, 10:36 PM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

Maybe the $>$ should be a $\geq$ (and the $\gcd(a_i,a_j)=1$ still be there). Otherwise it isn't number theory at all.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#5 h Jun 18, 2008, 10:48 AM • 2 Y

Y by Adventure10, UpvoteFarm

ZetaX wrote:

Maybe the $>$ should be a $\geq$ (and the $\gcd(a_i,a_j) = 1$ still be there). Otherwise it isn't number theory at all.

That looks more like a NT problem indeed. Do you have a solution for that problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

49 posts

Woett

#6 h Mar 4, 2023, 6:46 PM • 1 Y

Y by UpvoteFarm

A solution for when we only assume $a_{i+2} - a_{i+1} \ge a_{i+1} - a_i$ for all $i \ge 1$ , as suggested by ZetaX almost 15 years ago:

For a constant $c \in \mathbb{N}$ let $S_c = \{a_k, a_{k+1}, \ldots, a_{k+l-1}\}$ be the set of elements such that the difference $a_{k+i} - a_{k+i-1}$ is exactly equal to $c$ for all $i$ with $1 \le i \le l$ . I claim that $|S_c| = l < 2c-3$ for all $c \ge 3$ . Otherwise, note that $a_k, a_{k+1}, \ldots, a_{k+c-2}$ are all distinct modulo $c-1$ , and so are $a_{k+c-1}, a_{k+c}, \ldots, a_{k+2c-3}$ . That means that in each of these two subsequences there exists an element divisible by $c-1$ , which is not allowed by the assumption $\gcd(a_i, a_j) = 1$ . Likewise, $|S_1| < 3$ and $|S_2| < 5$ , as otherwise there must be two integers divisible by two or three respectively.

The inequalities $|S_1| < 3$ and $|S_2| < 5$ imply $a_5 - a_4 \ge 2$ and $a_{10} - a_9 \ge 3$ . The inequality $|S_c| < 2c-3$ for $c \ge 3$ can now be used to show via induction, that $a_{i+1} - a_i \ge n$ holds for all $i \ge n^2$ in general. Or, stated differently, $a_{i+1} - a_i \ge \left \lfloor \sqrt{i} \right \rfloor$ . This, in turn, implies that $\displaystyle a_{i+1} = a_1 + \sum_{j=1}^{i} (a_{j+1} - a_j) \ge 1 + \sum_{j=1}^i \left \lfloor \sqrt{j} \right \rfloor > \sum_{j=1}^i \frac{1}{2} \sqrt{j} > \int_0^i \frac{1}{2}\sqrt{j} \, dj = \frac{i^{3/2}}{3}$ .
Now the convergence of $\displaystyle \sum_{i=1}^{\infty} \frac{1}{a_i}$ is clear.

This post has been edited 5 times. Last edited by Woett, Mar 4, 2023, 6:48 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a