A real sequence

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A real sequence

G H J

Reveal topic tags

algebra proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran National Olympiad (3rd Round) 2001

The post below has been deleted. Click to close.

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

1275 posts

#1 h Jul 13, 2007, 6:38 AM • 6 Y

Y by Adventure10, Mango247, cubres, and 3 other users

Does there exist a sequence $\{b_{i}\}_{i=1}^\infty$ of positive real numbers such that for each natural $m$ : $b_{m}+b_{2m}+b_{3m}+\dots=\frac1m$

Z K Y

The post below has been deleted. Click to close.

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

2607 posts

#2 h Jul 16, 2007, 1:03 AM • 3 Y

Y by Adventure10, Mango247, cubres

http://www.mathlinks.ro/viewtopic.php?search_id=2008794938&t=152341

Z K Y

The post below has been deleted. Click to close.

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

56 posts

#3 h Jul 18, 2007, 8:29 PM • 2 Y

Y by Adventure10, cubres

Can we say this?

$\sum_{m=1}^{\infty}lim_{n\rightarrow{\infty}}(b_{m}+b_{2m}+...+b_{nm})=\sum_{m=1}^{\infty}{d(m)b_{m}}=\sum_{m=1}^{\infty}\frac{1}{m}$ (absurd)
where $d(m)$ is the number of divisor of m

Z K Y

The post below has been deleted. Click to close.

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

56 posts

#4 h Jul 24, 2007, 10:17 AM • 2 Y

Y by Adventure10, cubres

perfect_radio what do you think?It's possible.

Z K Y

The post below has been deleted. Click to close.

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

41 posts

crude

#5 h Jul 29, 2007, 8:37 PM • 5 Y

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

I guess, I found something interesting on this problem.
The idea is the following:
Write the sum $b_{m}+b_{2m}+b_{3m}+...=b_{m}+(b_{2m}+b_{4m}+...)+(b_{3m}+b_{6m}+...)+...-$
$-(b_{6m}+b_{12m}+...)-(b_{8m}+b_{16m}+...)+...=b_{m}+\frac{1}{2m}+\frac{1}{3m}+\frac{1}{5m}+...-$
$-\frac{1}{6m}-\frac{1}{10m}-\frac{1}{14m}...=\frac{1}{m}$ , from this we can see that
$b_{m}=\frac{1}{m}(1-\sum_{i\in P}{\frac{1}{i}}+\sum_{i,j\in P, i\neq j}{\frac{1}{ij}}-\sum_{i,j,k \in P, i\neq j\neq k, i\neq k}\frac{1}{ijk}+...)$ , where $P$ is the set of all prime numbers.
Clearly the sum in the brackets is independent of $m$ and generally of anything. There are two options, either it does not exist or it is some constant let's say $k$ . In latter case we have that
$k(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...)=1$ , which brings again to impossible result.

Z K Y

The post below has been deleted. Click to close.

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

889 posts

#6 h Feb 11, 2015, 4:51 AM • 2 Y

Y by Adventure10, cubres

Yes. Exclusiom-Inclusion Principle kills it.

Z K Y

The post below has been deleted. Click to close.

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

1502 posts

SCP

#7 h Apr 23, 2016, 12:57 PM • 3 Y

Y by Adventure10, Mango247, cubres

Sure, the solution of post 5 is correct?
As there has been working with infinitely many infinite series, it seems there will be trouble with the order of executing that sum.
Also post 3 seems like not concluding anything as $d(m)$ isn't bounded.

Z K Y

The post below has been deleted. Click to close.

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

1671 posts

pad

#9 h Dec 8, 2020, 10:43 AM • 1 Y

Y by cubres

Quote:

Determine whether there exists a sequence $a_1,a_2,\ldots$ of nonnegative reals such that
$a_{n}+a_{2n}+a_{3n}+\cdots=\frac1n$ for every positive integer $n$ .

No. Suppose there did. Let $S_k=\{ n\in \mathbb{N}:p_1\mid n, \text{ or } p_2\mid n, \ldots, \text{ or } p_k\mid n\}$ where we order the primes $\{p_1<p_2<\cdots\}$ . The idea is to ``interlace'' the sequences for $n=p_1,\ldots,p_k$ . Using CRT and Inclusion-Exclusion:
$\sum_{n\in S_k} a_n = \sum_{\substack{T\subset S_k \\ T\not=\emptyset}} (-1)^{|T|+1}\prod_{i\in T}\frac{1}{p_i} = 1-\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$ by expansion. Using the estimate $\log(1-\varepsilon)\le -0.01\varepsilon$ for $\varepsilon\in (0,1)$ , we have
$\log \prod_{i=1}^k\left(1-\frac{1}{p_i}\right) = \sum_{i=1}^k \log\left(1-\frac{1}{p_i}\right) \le \sum_{i=1}^k -0.01\cdot \frac{1}{p_i}=-0.01P_k$ where $P_k:=\sum_{i=1}^k 1/p_i$ . Therefore, since $\log$ is an increasing function, we have
$\begin{align*} \prod_{i=1}^k\left(1-\frac{1}{p_i}\right) \le e^{-0.01P_k} &\implies \sum_{n\in S_k}a_n \ge 1-\frac{1}{\left(e^{0.01} \right)^{P_k}}. \end{align*}$ Hence
$\begin{align*} 1-a_1=\sum_{i\ge 2}a_i \ge \sum_{n\in S_k} a_n \ge 1-\frac{1}{\left(e^{0.01} \right)^{P_k}} \implies a_1 \le \frac{1}{\left(e^{0.01} \right)^{P_k}}. \end{align*}$ But it is well-known that $P_k$ grows arbitrarily large varying $k$ , so this forces $a_1=0$ . Now, fix an $\ell$ . Let $b_n=\ell a_{\ell n}$ for each $n$ . Then $(b_n)$ is also a valid sequence, since
$b_n+b_{2n}+\cdots = \ell a_{\ell n}+\ell a_{2\ell n} + \cdots = \ell \cdot \frac{1}{\ell n} = \frac{1}{n}.$ Therefore, $b_1=0$ , so $\ell a_\ell=0$ , i.e. $a_\ell=0$ . Therefore, the entire sequence is $0$ , contradiction.

Remarks

This post has been edited 2 times. Last edited by pad, Dec 8, 2020, 9:35 PM

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#10 h Jul 25, 2021, 10:54 PM • 1 Y

Y by cubres

The answer is no. Assume for contradiction such a sequence exists, and let $P_n$ denote the first $n$ primes. By the Principle of Inclusion-Exclusion, $\frac1n-a_n=\lim_{k\to\infty}\sum_{T\subset P_k}\frac{(-1)^{|T|}}{n\prod_{p\in T}p}=\frac1n\lim_{k\to\infty}\sum_{T\subset P_k}\frac{(-1)^{|T|}}{\prod_{p\in T}p}=\frac{1-a_1}n.$ Solving, $a_n=\tfrac1na_1$ for all $n$ , so $1=\sum_{k=1}^\infty a_k=\sum_{k=1}^\infty\frac{a_1}k=a_1\sum_{k=1}^\infty\frac1k.$ Since $\sum_{k=1}^\infty a_k$ diverges, $a_1=0$ , which means that $a_n=0$ for all $n$ . This yields the desired contradiction.

Z K Y

The post below has been deleted. Click to close.

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

laikhanhhoang_3011

637 posts

laikhanhhoang_3011

#11 h Jul 26, 2021, 2:01 AM • 1 Y

Y by cubres

i think the idea of this problem related to Euler formula in Zeta Function

Z K Y

The post below has been deleted. Click to close.

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

93 posts

#12 h Nov 7, 2023, 4:36 PM • 1 Y

Y by cubres

Indeed.

Note that $a_1 + a_2 + \dots = 1$ and that $a_n \le \frac{1}{n}$ . However, we also have that
$\sum_{k}^{N} \mu(k) (a_k + a_{2k} + \dots) = \sum_{k}^N \frac{\mu(k)}{k}$ eventually contains all of $a_1$ through $a_N$ and thus has a limit of $1$ . This contradicts the fact that $\lim_{s \to 1^+} \frac{1}{\zeta(s)} = \lim_{s \to 1^+} \sum_k \frac{\mu(k)}{k}$ approaches $0$ which implies that this has a limit of $0$ .

Z K Y

The post below has been deleted. Click to close.

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

71 posts

#13 h Nov 13, 2024, 4:49 PM • 1 Y

Y by cubres

Let $D_i$ be the set of all positive integers with exactly $i$ prime factors, not necessarily distinct. Observe that
$a_n = 1 - \sum_{k=2}^{\infty} a_{kn} = 1 - \sum_{k=1}^{\infty} (-1)^{k+1} \left( \sum_{x \in D_k} \left( \sum_{i=1}^{\infty} a_{xkn} \right) \right) = \frac{a_1}{n}.$ $=\frac{1}{n}\left(1 - \sum_{k=1}^{\infty} (-1)^{k+1} \left( \sum_{x \in D_k} \left( \sum_{i=1}^{\infty} a_{xk} \right) \right)\right) = \frac{a_1}{n}.$ But this implies that
$a_1 + a_2 + a_3 + \dots = a_1 + \frac{a_1}{2} + \frac{a_1}{3} + \dots \neq 1$ which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

1522 posts

#14 h Feb 9, 2025, 2:56 AM • 1 Y

Y by cubres

Let $S_k$ denote the set of the first $k$ primes, now from PIE just notice that:
$\frac{1}{n}-b_n=\lim_{\ell \to \infty} \sum_{S \subset S_{\ell}} \frac{(-1)^{|S|+1}}{n \cdot \prod_{p \in S} p}=\frac{1}{n} \cdot \lim_{\ell \to \infty} \sum_{S \subset S_{\ell}} \frac{(-1)^{|S|+1}}{\prod_{p \in S} p}=\frac{1-b_1}{n} \implies b_n=\frac{b_1}{n}$ But now we have $b_1 \left(1+\frac{1}{2}+\cdots \right)=1$ which by divergence of harmonic series gives $b_1=0$ but then $b_i=0$ for all positive integer $i$ which clearly fails, so no such sequence exists.

Z K Y

The post below has been deleted. Click to close.

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

156 posts

Ritwin

#15 h Feb 27, 2025, 6:39 PM

Y by

No, there does not. We can prove by PIE that for any $n = gk$ , $\sum_{\gcd(m,n)=g} a_m = \frac{\varphi(n/g)}{n} = \frac1g \cdot \frac{\varphi(k)}{k}.$ On the other hand, $\tfrac{\varphi(k)}{k}$ can be arbitrarily small, so the left sum must be $0$ . Since $g$ was arbitrary, every $a_i = 0$ . This is obviously a contradiction.

Proof (of $\varphi(k)/k$ arbitrarily small). Enumerate the primes $p_1 < p_2 < \cdots$ and take $k = p_1 p_2 \cdots p_N$ . We have $\frac{\varphi(k)}{k} = \prod_{i=1}^N \left(1 - \frac{1}{p_i}\right) \leq \exp \left(-\sum_{i=1}^N \frac{1}{p_i}\right)$ since $e^{-t} \geq 1-t$ . Since $\textstyle{\sum} \tfrac{1}{p_i}$ diverges, the right side is arbitrarily small, meaning $\varphi(k)/k$ gets arbitrarily small. $\square$

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#16 h Mar 2, 2025, 5:20 AM

Y by

This problem is ridiculously cute. The answer is no.

Let $k$ be any positive integer, and let $S_k$ denote the set of all positive integers relatively prime to the first $k$ primes $p_1, p_2, \dots, p_k$ . By principle of inclusion-exclusion, $\lim_{k \to \infty} \sum_{d \in S_k} a_d = \lim_{k \to \infty} \frac{\varphi(p_1p_2 \dots p_k)}{p_1 p_2 \dots p_k} = \lim_{k \to \infty} \prod_{i=1}^k \left(1-\frac 1{p_i}\right).$ This converges to zero as its reciprocal is lower bounded by $\lim_{k \to \infty}\prod_{i=1}^k \left(1+\frac 1{p_i - 1}\right) > \lim_{k \to \infty}\prod_{i=1}^k \left(1+\frac 1{p_i}\right) = \sum_{i=1}^\infty \frac 1i = \infty.$ But $a_1$ always falls in the given set, so $a_1 = 0$ . Similarly, by scaling the sequence, we get $a_n = 0$ for every positive integer $n$ .

This post has been edited 1 time. Last edited by HamstPan38825, Mar 2, 2025, 5:21 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a