4
$\begingroup$

Problem :A sequence $a_1,a_2,\dots$ satisfy $$ \sum_{i =1}^n a_{\lfloor \frac{n}{i}\rfloor }=n^{10}, $$ for every $n\in\mathbb{N}$. Let $c$ be a positive integer. Prove that, for every positive integer $n$, $$ \frac{c^{a_n}-c^{a_{n-1}}}{n} $$ is an integer.

I try :

Note that the required proposition is true if both $a_n\geqslant n$ and $\phi (n)\mid a_n-a_{n-1}$ is true for all positive integer $n>1$. From the condition given, we get that $a_1=1$ and \begin{align*} (n+1)^{10}-n^{10}-1& =\sum_{j=1}^{n}{\left( a_{\lfloor \frac{n+1}{j}\rfloor }-a_{\lfloor \frac{n}{j}\rfloor }\right) }\\ & =\sum_{\substack{j\mid n+1 \\1\leqslant j<n+1}}{\left( a_{\frac{n+1}{j}} -a_{\frac{n+1}{j}-1} \right) } \\ & =\sum_{\substack{d\mid n+1 \\d>1}}{ (a_d-a_{d-1})} . \end{align*} Following work I can't

$\endgroup$
4
$\begingroup$

You are in the right direction. Differencing yields $$\begin{eqnarray} n^{10} - (n-1)^{10} &=& a_1 +\sum_{1\leq i \leq n-1} (a_{\lfloor \frac{n}{i}\rfloor }-a_{\lfloor \frac{n-1}{i}\rfloor })\\ &=&a_1 + \sum_{i|n, i<n} (a_{\frac{n}{i} }-a_{\frac{n}{i}-1 })\\ &=&a_1 + \sum_{i|n, i>1} (a_{i }-a_{i-1 }) = \sum_{i|n} (a_{i }-a_{i-1 }) \end{eqnarray}$$ if we let $a_0 = 0$. Define $b_n = a_n - a_{n-1}$ and $p(n) = n^{10} - (n-1)^{10}$. By Mobius inversion formula, (see https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula) we have $$ b_n = \sum_{j|n} p(j)\mu(\frac{n}{j}). $$ What we show first is that $\phi(n) $ divides each $b_n$ for all $n\geq 1.$ To this end, we show the following claim: for each $r\geq 0$, $\sum_{j|n} j^r\mu(\frac{n}{j})$ has $\phi(n)$ as its factor. Proof goes like this. Let $$c_n = \sum_{j|n} j^r\mu(\frac{n}{j}).$$ Observe that $c_1 = 1$, hence $\phi(1) | c_1$. We first show $\phi(n)|c_n$ for $n = p^k$ where $p$ is a prime. This follows easily since $$ c_{p^k} = p^{rk} - p^{r(k-1)}, $$ and $$ \phi(p^k) = p^k - p^{k-1}. $$ (Note that $x-y | x^r - y^r$.) Next we show that $c_n$ is multiplicative, that is, for $p,q$ such that $(p,q)=1$, it holds that $c_{pq} = c_pc_q$. This also follows easily from $$\begin{eqnarray} c_{pq} &=&\sum_{j|pq} j^r\mu(\frac{pq}{j}) \\ &=& \sum_{n|p, m|q} (nm)^r\mu(\frac{pq}{nm})\\ &=&\sum_{n|p, m|q} n^r\mu(\frac{p}{n})\cdot m^r\mu(\frac{q}{m})\\ &=& \sum_{n|p} n^r\mu(\frac{p}{n})\cdot \sum_{m|q}m^r\mu(\frac{q}{m})\\ &=& c_p\cdot c_q. \end{eqnarray}$$ Since $\phi(n)$ is also multiplicative, these two facts prove the claim.

So far we've shown that for every monomial $j^r$, it holds that $\phi(n) |\sum_{j|n} j^r\mu(\frac{n}{j})$. Thus it holds for any polynomial with integer coefficients, and especially for $p(j)$. This shows $$ \phi(n) \:|\: b_n = \sum_{j|n} p(j)\mu(\frac{n}{j}), $$ as we wanted.
It remains to show $a_n \geq n$. Assume $c\cdot j^{10} \leq a_j \leq j^{10}$ for $j=1,2,\ldots,n-1$ for some $0<c<1$. Then we have $$\begin{eqnarray} a_n &=& n^{10} - \sum_{2\leq i \leq n} a_{\lfloor \frac{n}{i}\rfloor }\\ &\geq & n^{10} - n^{10}\sum_{2\leq i \leq n} \frac{1}{i^{10}} \\ &\geq & n^{10} (1-\sum_{2\leq i <\infty} \frac{1}{i^{10}}), \end{eqnarray}$$ and $a_n \leq n^{10}$. If we let $c = 1-\sum_{i=2}^{\infty}\frac{1}{i^{10}}\in (0.99,1)$, then by induction hypothesis, it holds for every $n\in \mathbb{N}$ once if we prove it for $n=1$. But this is obviously true, since $a_1 = 1$. Finally, we see that $$ a_n \geq c\cdot n^{10} \geq (c\cdot 2^9)\cdot n >500n $$ for all $n\geq 2$, establishing $a_n \geq n$.

$\endgroup$
1
$\begingroup$

Something maybe helpful:

Denote $b_n=a_n-a_{n-1}$ and $f(n)=n^{10}-(n-1)^{10}$.

For any prime number $p$, we have $$b_p=a_{p}-a_{p-1}=p^{10}-(p-1)^{10}-1=f(p)-1$$ Notice that for any $n=p^m$ where $m$ is a positive integer : $$b_{p^m}=f(p^m)-1-\sum_{k=1}^{m-1}{b_{p^k}}$$ then by mathematical induction, we can get that $$b_{p^m}=f(p^m)-f(p^{m-1})=(p^m)^{10}-(p^m-1)^{10}-(p^{m-1})^{10}+(p^{m-1}-1)^{10}$$ For two different prime number $p,q$, we have $$b_{pq}+b_p+b_q=f(pq)-1$$ which implies that $$b_{pq}=f(pq)-f(p)-f(q)+1$$ then by mathematical induction, we can get that $$b_{p_1p_2\cdots p_k}=\sum^{k}_{i=1}(-1)^{k-i}\sum_{1\leq k_1<k_2<\cdots<k_i\leq k}{f(p_{k_1}p_{k_2}\cdots p_{k_i})}+(-1)^{k}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.