Mobius function

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

Mobius function

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.

44 posts

#1 h Apr 28, 2025, 12:14 PM

Y by

Consider a sequence $(a_n)$ that satisfies:
$\sum_{i=1}^{n} a_{\left\lfloor \frac{n}{i} \right\rfloor} = n^k$
Let $c$ be a positive integer. Prove that for all integers $n > 1$ , we have:
$\frac{c^{a_n} - c^{a_{n-1}}}{n} \in \mathbb{Z}$

Z K Y

The post below has been deleted. Click to close.

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

44 posts

#2 h Apr 28, 2025, 1:47 PM

Y by

bump.....

Z K Y

The post below has been deleted. Click to close.

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

61 posts

#3 h Apr 28, 2025, 5:56 PM

Y by

The statement is obvious for $k=1$ , thus assume $k>1$
Note that $\left\lfloor\frac{n+1}{i}\right\rfloor=\left\lfloor\frac{n}{i}\right\rfloor+1$ iff $i\;|\;n+1$ , $a_1=1$
Therefore $(n+1)^k-n^k=1+\sum^n_{i=1}(a_{\lfloor\frac{n+1}{i}\rfloor}-a_{\lfloor\frac{n}{i}\rfloor})=1+\sum_{d|n+1,d<n+1}(a_{\frac{n+1}{d}}-a_{\frac{n+1}{d}-1})$
Let $b_n=a_n-a_{n-1}$ for $n>1$ , $b_1=1$
We have $\sum_{d|n}b_d=n^k-(n-1)^k$ for all $n$
Using Mobius inversion theorem, $b_n=\sum_{d|n}\mu\left(\frac{n}{d}\right)(d^k-(d-1)^k)$
Note that the function $f_m(n):=\sum_{d|n}\mu\left(\frac{n}{d}\right)d^m$ is multiplicative, so $f_m(n)=\prod_{p|n}(p^{mv_p(n)}-p^{m(v_p(n)-1)})$ divisible by $\varphi(n)$
But $b_n$ equals sum of the $f_m(n)$ with integer coefficients, so $b_n$ is divisible by $\varphi(n)$
Now we prove: $a_n\geq n,\forall n$ using induction
For $n=1,2,3$ the statement is true, assume it is true for all $1,2,...,n-1$ $(n\geq4)$ .
We have $a_n\leq n^k$ for all $1,2,...,n$
So $n^k=a_n+\sum_{i=2}^n a_{\lfloor\frac{n}{i}\rfloor}\leq a_n+\sum_{i=2}^n\left\lfloor\frac{n}{i}\right\rfloor^k\leq a_n+n^k\sum_{i=2}^n\frac{1}{i^k}$
So $a_n\geq n^k(1-\sum_{i=2}^n i^{-k})\geq n^k(1-\sum_{i=2}^n i^{-2})> n^2(2-\frac{\pi^2}{6})>0.3n^2>n$ for $n\geq 4$ , induction complete
Now we are ready to prove the claim
Write $n=ab$ , every prime factor of $a$ divides $c$ , and $(b,c)=1$ , also $(a,c)=1$
$b_n$ is divisible by $\varphi(n)$ so $c^{a_n}-c^{a_{n-1}}$ is divisible by $b$ (1)
For $p|a$ , we have $v_p(c^{a_n}-c^{a_{n-1}})\geq n-1 (a_n\geq n \forall$ n $)\geq v_p(n)$ (2)
From (1) (2) we have $c^{a_n}-c^{a_{n-1}}$ is divisible by $n$ , problem solved

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a