I am looking for an upper bound of the following sum $$ S_p:= \sum_{j=1}^p \frac{p+1}{p-j+1} \frac1{2^j}. $$ The upper bound should be independent of $p$, of course. Numerical experiments indicate that $$ S_p \le \frac53 $$ with the maximum attained for $p=3,4$. However, I am not able to prove it.

I could only prove $S_p \le 3$. Here is, what I did: First, we see $$ \frac{p+1}{p-j+1} = 1 + \frac j{p-j+1}\le 1+j, $$ hence $$ S_p \le \sum_{j=1}^p (1+j) \frac1{2^j} . $$ Using the power series $$ (1-x)^{-2} = \sum_{j=0}^\infty (1+j) x^j , \ |x|<1, $$ I can estimate $$ S_p \le (1-\frac12)^{-2} -1 = 3. $$ How can the bound be improved?


First, note that that the change of summation index $j\leftarrow p+1-j$ shows that $$ S_p=\frac{p+1}{2^{p+1}}\sum_{j=1}^p\frac{2^j}{j} $$ Thus $$ \frac{2^{p+1}}{p+1}S_p=\sum_{j=1}^p\frac{2^j}{j}=\frac{2^p}{p}+\frac{2^{p}}{p}S_{p-1} $$ Similarly$$\eqalign{ \frac{2^{p+2}}{p+2}S_{p+1} &=\frac{2^{p+1}}{p+1}+\frac{2^{p+1}}{p+1}S_{p}\cr &=\frac{2p}{p+1}\left(\frac{2^{p+1}}{p+1}S_p-\frac{2^{p}}{p}S_{p-1}\right)+\frac{2^{p+1}}{p+1}S_{p} }$$ This can be rearranged as follows $$\eqalign{ \frac{S_{p+1}}{S_p} &= \frac{(p+2)(3p+1)}{2(p+1)^2}-\frac{p+2}{2(p+1)}\cdot\frac{S_{p-1}}{S_p} }$$ Now, If for some $p\ge2$ we have $S_p<S_{p-1}$ then $$ \frac{S_{p+1}}{S_p}<\frac{(p+2)(3p+1)}{2(p+1)^2}-\frac{p+2}{2(p+1)}=\frac{p(p+2)}{(p+1)^2}<1. $$ That is $S_{p+1}<S_p$, and we have proved that $$ S_p<S_{p-1}\quad \Longrightarrow\quad S_{p+1}<S_p $$ Now it is easy to check that $S_5=\frac{8}{5}<\frac{5}{3}=S_4$, hence the sequence $(S_p)_p$ is decreasing starting from $p=4$. Since $$S_1=1~<S_2=\frac{3}{2}<S_3=\frac{5}{3}=S_4=\frac{5}{3}$$ we conclude that $$\max\{S_p:p\geq 1\}=\frac{5}{3}$$ and it is exactly attained at $p=3,4$.$\qquad\square$

Remark. as Did suggested, we have also the simple lower bound $$ S_p\geq\frac{p+1}{2^{p+1}}\cdot\frac{2^{p+1}-2}{p} $$ So, $\ell~{\buildrel{\rm def}\over =}~\lim\limits_{p\to\infty}S_p\geq 1$. This implies that $$\inf\{S_p:p\geq 1\}=1=S_1.$$ Finally, with a little more work, it can be proved that $\ell=1$.

  • $\begingroup$ Nice. Although the OP does not ask for lower bounds, you might want to add that $S_p\to1$ when $p\to\infty$ hence $\min\{S_p;p\geqslant1\}=1$ and $\inf\{S_p;p\geqslant p_0\}=1$ for every $p_0\geqslant1$. $\endgroup$ – Did Jul 15 '14 at 10:09
  • $\begingroup$ @Did, Yes you are right, It is done. $\endgroup$ – Omran Kouba Jul 15 '14 at 10:54

Hint: Rewrite the rational function $\frac{p+1}{p+1-j}$ as an infinite geometric series, i.e.,


This expansion is valid since the variable $j$ only ranges from $0\le j \le p<p+1$, hence $|\frac{j}{p+1}|<1.$

Then, by reversing the order of summation we get:

$$S_p=\sum_{j=1}^{p}\sum_{k=0}^{\infty}\left(\frac{j}{p+1}\right)^k\frac{1}{2^j}\\ =\sum_{k=0}^{\infty}\sum_{j=1}^{p}\left(\frac{j}{p+1}\right)^k\frac{1}{2^j}\\ =\sum_{k=0}^{\infty}\frac{1}{(p+1)^k}\sum_{j=1}^{p}\frac{j^k}{2^j}.$$

  • $\begingroup$ I do not see how to conclude: Using the estimate $j^k\le p^k$, I obtain $S_p \le \frac12 (p+1)$ ?? $\endgroup$ – daw Jul 15 '14 at 7:40

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.