15
$\begingroup$

In a much larger problem, I need to solve for $x_n$ the equation $$\sum_{i=0}^n (n+i)^{x_n}=(2n+1)^{x_n}$$ where $n$ can be large.

From a numerical point of view, it does not make any practical difficulty solving instead $$\log\left(\sum_{i=0}^n (n+i)^{x_n} \right)={x_n}\log(2n+1)$$ which is "almost" finding the intersection of two straight lines.

My first surprise, working with small values of $n$, was to notice that the solution is almost linearly dependent on $n$.

Working with large numbers, what I noticed is the following $$\left( \begin{array}{cc} n & \frac {x_n} n \\ 10^1 & 1.351611135 \\ 10^2 & 1.382828492 \\ 10^3 & 1.385947786 \\ 10^4 & 1.386259704 \end{array} \right)$$ and the ratio "seems" to converge to something.

So, my questions :

  • Could we prove the linear dependency of $x_n$ to $n$ ?
  • Could we prove that $\frac {x_n} n$ tends to a limit ?
  • If there is a limit, what could be this number ? In other words, would it be possible to establish the asymptotics of $x_n$ ?

Edit after answers

After the beautiful answers I received from Professor Vector and Raymond Manzoni (who made the problem more general), I solved, for $n=10^4$, the equation$$\sum_{i=0}^n (n+i)^{x_n}=(2n+a)^{x_n}$$ In the table below are reproduced the results for the computed ratio $\frac {x_n} n$ and the value computed for $y_a=-2\log(b)$ where $b$ is the positive solution of $1-b=b^a$. $$\left( \begin{array}{cc} a & \frac {x_n} n & y_a\\ 1 & 1.38626 &1.38629 \\ 2 & 0.96240 &0.96242 \\ 3 & 0.76448 &0.76449 \\ 4 & 0.64457 &0.64457 \\ 5 & 0.56240 &0.56240 \\ 6 & 0.50184 &0.50183 \\ 7 & 0.45496 &0.45495 \\ 8 & 0.41739 &0.41737 \\ 9 & 0.38646 &0.38644 \end{array} \right)$$

Concerning the case where $a=1$, it is interesting to compare the results I gave with the asymptotics Raymond Manzoni gave in a comment. $$\frac {x_n} n=2\log(2)-\frac{\log(2)}{2n}+O\left(\frac 1 {n^2} \right)$$ $$\left( \begin{array}{cc} n & \frac {x_n} n &2\log(2)-\frac{\log(2)}{2n}\\ 10^1 & 1.351611135 &1.351637002\\ 10^2 & 1.382828492 &1.382828625\\ 10^3 & 1.385947786 &1.385947788\\ 10^4 & 1.386259704 &1.386259704 \end{array} \right)$$ I do not think that I could add any comment !

$\endgroup$
  • 3
    $\begingroup$ Of course, the closeness to $2\ln2=1.38629436111\ldots$ could be a coincidence, but I guess it's more. $\endgroup$ – Professor Vector Aug 1 '17 at 9:34
  • $\begingroup$ @ProfessorVector. I noticed that but I preferd not to mention it. It could be funny, isn't it ? $\endgroup$ – Claude Leibovici Aug 1 '17 at 9:37
  • $\begingroup$ I think I can prove that limit, but not at work. $\endgroup$ – Professor Vector Aug 1 '17 at 10:08
  • $\begingroup$ @ProfessorVector. I shall wait, then ! Thanks. $\endgroup$ – Claude Leibovici Aug 1 '17 at 10:10
  • 2
    $\begingroup$ Yay! $2\ln\phi=0.962423650119\ldots$ ($\phi$ being Golden Ratio) $\endgroup$ – Professor Vector Aug 1 '17 at 10:30
13
$\begingroup$

Let's investigate the equation $$\sum_{i=0}^n (n+i)^{x_n}=(2n+1)^{x_n}:$$ As $i$ goes from $0$ to $n$, $n+i$ goes from $n$ to $2n$. If we reorder the sum upside down, and divide both sides by $(2n+1)^{x_n}$, we get $$\sum_{k=1}^{n+1}\left(\frac{2n+1-k}{2n+1}\right)^{x_n}=\sum_{k=1}^{n+1}\left(1-\frac{k}{2n+1}\right)^{x_n}=1.$$ Using the elementary inequality $$1-\frac{k}{2n+1}\le\left(1-\frac1{2n+1}\right)^k$$ and setting $$\lambda_n=\left(1-\frac1{2n+1}\right)^{x_n},$$ the equation gives $$1\le\sum_{k=1}^{n+1}(\lambda_n)^k<\sum_{k=1}^\infty(\lambda_n)^k=\frac{\lambda_n}{1-\lambda_n}.$$ So $\lambda_n>1/2,$ meaning $$x_n<\frac{\ln 2}{\ln\frac1{1-1/(2n+1)}}<(2n+1)\ln 2,\tag{1}$$ since $\ln\frac1{1-x}>x$ for $1>x>0.$
The lower bound for $x_n$ is somewhat more technical:
We have $$1-\frac{k}{2n+1}=\frac1{1+\frac{k}{2n+1-k}}\ge\left(\frac1{1+\frac{1}{2n+1-k}}\right)^k\ge\left(\frac1{1+\frac{1}{2n+1-\sqrt{n}}}\right)^k$$ for $k\le\sqrt{n}.$ Setting $$\mu_n=\left(\frac1{1+\frac{1}{2n+1-\sqrt{n}}}\right)^{x_n},$$ we obtain the estimate $$1\ge\sum_{k=1}^{\lfloor\sqrt{n}\rfloor}\left(1-\frac{k}{2n+1}\right)^{x_n}\ge\sum_{k=1}^{\lfloor\sqrt{n}\rfloor}(\mu_n)^k=\frac{\mu_n}{1-\mu_n}\left(1-(\mu_n)^{\lfloor\sqrt{n}\rfloor}\right).$$ Clearly, this means $\mu_n\le1/(2-\epsilon_n),$ where $\epsilon_n=O(c^\sqrt{n})$ with some $c<1.$ This means $$x_n\ge\frac{\ln(2-\epsilon_n)}{\ln\left(1+\frac{1}{2n+1-\sqrt{n}}\right)}>(2n+1-\sqrt{n})\ln(2-\epsilon_n),\tag{2}$$ since $\ln(1+x)<x$ for $x>-1.$
(1) and (2) together imply $$\left(2+\frac1n-\frac1{\sqrt{n}}\right)\ln(2-\epsilon_n)<\frac{x_n}{n}<\left(2+\frac1n\right)\ln2,$$ and thus, $$\lim_{n\rightarrow\infty}\frac{x_n}{n}=2\ln2.$$
In the case of the equation $$\sum_{i=0}^n (n+i)^{x_n}=(2n+2)^{x_n},$$ we get $$\sum_{k=2}^{n+2}\left(1-\frac{k}{2n+2}\right)^{x_n}=1,$$ so the equation for $\lambda=\lim_{n\rightarrow\infty}\lambda_n$ becomes not $\lambda/(1-\lambda)=1,$ but $\lambda^2/(1-\lambda)=1,$ i.e. $\lambda=1/\phi.$

$\endgroup$
  • $\begingroup$ This is really a beautiful and elegant answer to the problem. Thank you very much ! $\endgroup$ – Claude Leibovici Aug 2 '17 at 4:12
  • $\begingroup$ One direction is a bit technical and not so pretty, but that's inevitable, because your sum is dominated by far less than $n$ largest terms $(1+\epsilon)\ln n,$ I'd say. I used $\sqrt{n}$ only as a convenient compromise. $\endgroup$ – Professor Vector Aug 2 '17 at 4:15
10
$\begingroup$

Let's use Euler–Maclaurin to approximate your sum for large $n$ ($p$ is a fixed integer) : $$\sum_{i=0}^n f(i) = \int^n_0 f(t)\,dt + \frac{f(n) + f(0)}{2} + \sum_{k=1}^{\lfloor p/2\rfloor} \frac{B_{2k}}{(2k)!} (f^{(2k - 1)}(n) - f^{(2k - 1)}(0)) + R$$ For $\,f(t):=(n+t)^x\;$ this becomes : \begin{align} \sum_{i=0}^n (n+i)^x &= \int^n_0 (n+t)^x\,dt + \frac{(2n)^x + (n)^x}{2} + \sum_{k=1}^{\lfloor p/2\rfloor} \frac{B_{2k}}{(2k)!} (f^{(2k - 1)}(n) - f^{(2k - 1)}(0)) + R\\ &=\frac{\left(2^{x+1}-1\right)n^{x+1}}{x+1}+ \frac{(2^x+1)n^x}{2} + \sum_{k=1}^{\lfloor p/2\rfloor} \frac{B_{2k}}{(2k)!} (f^{(2k - 1)}(n) - f^{(2k - 1)}(0)) + R\\ \end{align}

Let's first neglect the Bernoulli terms and remainder then we want $x$ solution of :

$$\frac{\left(2^{x+1}-1\right)n^{x+1}}{x+1}+ \frac{(2^x+1)n^x}{2}\approx(2n+a)^{x}$$ for $n\gg 1\,$ and $\,x:=ny\;$ we may neglect the $\pm 1$ terms to get : $$\frac{(2n)^{ny+1}}{ny}+\frac{(2n)^{ny}}{2}\approx(2n)^{ny}\left(1+\frac a{2n}\right)^{2n\,y/2}$$ simplification and limit as $n\to \infty$ at the right leaves : $$\frac{2}{y}+\frac{1}{2}\approx e^{\,ay/2}$$ admitting the approximate solution $\,y\approx 1.358\,$ for $a=1$.

Incorporating the two first Bernoulli corrections we get instead : $$\frac 12+\frac 2y+\frac y{24}-\frac {y^3}{5760}\approx e^{\,ay/2}$$ where $\dfrac 1{24}=\dfrac {B_{2}}{2^1 2!}$ and $\dfrac {-1}{5760}=\dfrac {B_{4}}{2^3 4!}\;$ suggesting us to add all the Bernoulli terms to obtain the usual generating function $\;\displaystyle \frac 1{1-e^{-y/2}}\;$ at the left. As $n\to\infty$ the problem becomes to solve : $$1-e^{-y/2}=e^{-ay/2}$$ i.e. obtain the positive solution of $\,1-b=b^a\;$ and conclude with $\;y=2\ln(1/b)$.

For $a=1\,$ this returns the wished $\,y=2\ln(2)$ while for $a=2\,$ you'll obtain $y=2\ln(\phi)$ ($\phi$ the golden ratio) : both solutions proposed by Professor Vector (+1) !

ADDITIONS: I will further conjecture following expansion for $a=1$ : $$\frac {x_n}n=\ln(2)\left(2-\frac 1{2n}+\frac {-\frac{25}{24}+\frac 32\ln(2)}{n^2}+\frac{-\frac {169}{96}+\frac{55}8\ln(2)-\frac{25}4\ln(2)^2}{n^3}\right)+O\left(\frac 1{n^4}\right)$$


Claude Leibovici suggested (privately) to replace $n$ by a fixed $a$ in the previous problem that is to solve $\;\displaystyle\sum_{i=0}^n (a+i)^x= (a+n+k)^{x}$.
Let's use the same method with $\,f(t):=(a+t)^x\;$ : $$\sum_{i=0}^n (a+i)^x \sim \frac{(a+n)^{x+1}-a^{x+1}}{x+1}+ \frac{(a+n)^x + a^x}{2} + \sum_{k=1}^{\lfloor p/2\rfloor} \frac{B_{2k}}{(2k)!} (f^{(2k - 1)}(n) - f^{(2k - 1)}(0))$$

without the Bernoulli terms we would have :

$$\frac{(a+n)^{x+1}-a^{x+1}}{x+1}+ \frac{(a+n)^x + a^x}{2} \approx(a+n+k)^{x}$$

for $\,n\gg 1\,$ and $\,x=ny\,$ we may neglect the powers of $a$ alone and the $+1$ : $$\frac{(a+n)^{ny+1}}{ny}+\frac{(a+n)^{ny}}{2}\approx(a+n)^{ny}\left(1+\frac k{a+n}\right)^{(a+n)\,y-ay}$$

After division by $(a+n)^{ny}$ and for $n \gg 1$ : $$\frac{a+n}{ny}+\frac 12\approx e^{ky}\left(1+\frac k{a+n}\right)^{-ay}$$

or as $ n\to\infty$ : $$\frac 1y+\frac{1}{2}\approx e^{\,ky}$$ with a solution $y$ near to $\ln(2)$ for $k=1$.

Adding all the Bernoulli terms gives at the left $\dfrac 1{1-\exp(-y)}\;$ so that we must solve : $1-\exp(-y)=\exp(-ky)$ or, again, $1-b=b^k$ followed this time by $y = \ln(1/b)$.

I'll conclude with this (conjectured) expansion for $k=1$ : $$\frac {x_n}n = \ln(2)\left(1+\frac{a-1/2}n +\frac {-\frac{25}{12}+3\ln(2)}{n^2}\right)+ O\left(\frac 1{n^3}\right)$$

$\endgroup$
  • $\begingroup$ Hi Raymond ! Long time no speak. This is really a beautiful and elegant answer to the problem. Thank you very much ! $\endgroup$ – Claude Leibovici Aug 2 '17 at 4:13
  • $\begingroup$ Glad you liked this @Claude (fine question and edit btw !). Expansions in negative powers of $n$ are of interest too getting $\;\displaystyle x_n=2\ln(2)-\frac {\ln(2)}{2\,n}+O\left(\frac 1{n^2}\right)\;$ and more if needed. Cheers, $\endgroup$ – Raymond Manzoni Aug 2 '17 at 6:36
  • $\begingroup$ My method can't give the asymptotics, it's too elementary for that. I did compute the limit for $a=3$, though, it's 0.76449017168007128265871699836971. $\endgroup$ – Professor Vector Aug 2 '17 at 7:02
  • $\begingroup$ @Professor Vector: Corresponding to alpha's answer : $$2\ln\left(2+2^{2/3}\sqrt[3]{29-3\sqrt{93}}+2^{2/3}\sqrt[3]{29+3\sqrt{93}}\right)-2\ln(6)$$. Answer of different kinds are always appreciated! Cheers, $\endgroup$ – Raymond Manzoni Aug 2 '17 at 7:23
  • $\begingroup$ @Claude Leibovici: I added two more detailed expansions that could interest you! Cheers, $\endgroup$ – Raymond Manzoni Aug 4 '17 at 0:26
4
$\begingroup$

Using Bernoulli's Inequality, $$ \begin{align} \frac{\left(1-\frac{k+1}{2n+3}\right)^{n+\frac32}}{\left(1-\frac{k+1}{2n+1}\right)^{n+\frac12}} &=\left(1-\frac{k+1}{2n+3}\right)\left(\frac{2n+2-k}{2n+3}\frac{2n+1}{2n-k}\right)^{n+\frac12}\\ &=\left(1-\frac{k+1}{2n+3}\right)\left(1+\frac{2k+2}{(2n+3)(2n-k)}\right)^{n+\frac12}\\[9pt] &\ge\left(1-\frac{k+1}{2n+3}\right)\left(1+\frac{(2n+1)(k+1)}{(2n+3)(2n-k)}\right)\\[9pt] &=1+\frac{2(k+1)^2}{(2n-k)(2n+3)^2}\\[12pt] &\ge1 \end{align} $$ That is, $\left(1-\frac{k+1}{2n+1}\right)^{n+\frac12}$ is increasing in $n$.

Therefore, by Monotone Convergence, $$ \begin{align} \lim_{n\to\infty}\sum_{k=0}^n\left(\frac{n+k}{2n+1}\right)^{\left(n+\frac12\right)a} &=\lim_{n\to\infty}\sum_{k=0}^n\left(\frac{2n-k}{2n+1}\right)^{\left(n+\frac12\right)a}\\ &=\lim_{n\to\infty}\sum_{k=0}^n\left(1-\frac{k+1}{2n+1}\right)^{\left(n+\frac12\right)a}\\ &=\sum_{k=0}^\infty e^{-(k+1)a/2}\\ &=\frac{e^{-a/2}}{1-e^{-a/2}} \end{align} $$ The $a$ that gives the limit equal to $1$ is $$ a=2\log(2) $$

$\endgroup$
  • $\begingroup$ Strictly speaking, you don't show that the exact solution $x_n$ is approximately $2\ln2(n+1/2)$ (ratio of arguments $\rightarrow1$ as $n\rightarrow\infty$), but that the latter is an approximate solution (function values $\rightarrow1$). That's not necessarily the same thing, but equivalence is easy to show in this case, as the convergence is uniform in $a$ in every finite interval, due to monotony, again (Dini's theorem). $\endgroup$ – Professor Vector Aug 2 '17 at 18:57
  • $\begingroup$ Another nice solution using a quite different path. Thank you very much ! $\endgroup$ – Claude Leibovici Aug 3 '17 at 4:30

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.