Simplify the expression of binom

Question

Any one knows how to simplify this expression or finding upper bound of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}$$ where $0<a<1$ is constant.

Thanks a lot.

Answer 1

Rewrite it as:

$$\sum_{k=1}^{2n+1} a^k\sum_{0\leq i<j\leq n+1}_{i+j=k} \binom{k}{i}\leq \sum_{k=1}^{2n+1}a^k \frac{1}{2}\sum_{i=0}^{k} \binom{k}{i} = \frac{1}{2}\sum_{k=1}^{2n+1} (2a)^k = a\frac{1-(2a)^{2n+1}}{1-2a}$$

When $a=\frac{1}{2}$ this upper bound is $\frac{2n+1}{2}$

This gives about the same bound as Jack's answer when $a$ is small, but a much better bound when $a$ is close to $1$.

Answer 2

For a fixed $j$, we have: $$\sum_{i=0}^{+\infty}\binom{j+i}{i}x^i = \frac{1}{(1-x)^{j+1}}\tag{1}$$ hence the original sum is trivially bounded by: $$\frac{1}{1-a}\sum_{j=1}^{n+1}\frac{a^j}{(1-a)^j}=\frac{\left(\frac{a}{1-a}\right)-\left(\frac{a}{1-a}\right)^{n+2}}{1-2a},\tag{2}$$ but obviously we included a lot of unnecessary terms in $(1)$. In order to make things more symmetric, we may consider that: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1}a^{i+j}\binom{i+j}{i}=\sum_{j=0}^{n+1}\sum_{i<j}a^{i+j}\binom{i+j}{i}=\frac{1}{2}\left(\sum_{j=0}^{n+1}\sum_{i=0}^{n+1}a^{i+j}\binom{i+j}{i}-\sum_{k=0}^{n+1}a^{2k}\binom{2k}{k}\right)$$ due to the symmetry of the binomial coefficient $\binom{i+j}{i}=\binom{i+j}{j}$. Now, assuming $\alpha<\frac{1}{2}$: $$\sum_{k=0}^{+\infty}a^{2k}\binom{2k}{k}=\frac{1}{\sqrt{1-4a^2}},$$ and: $$\begin{eqnarray*}\sum_{k>(n+1)}a^{2k}\binom{2k}{k}&=&\sum_{k>(n+1)}\frac{a^{2k}}{2\pi}\int_{0}^{2\pi}(1+e^{i\theta})^{2k}e^{-ki\theta}\,d\theta\\&=&\frac{1}{2\pi}\int_{0}^{2\pi}\frac{(a^2(2+2\cos\theta))^{n+2}}{1-a^2(2+2\cos\theta)}d\theta\\&=&\frac{(2a)^{2n+4}}{2\pi}\int_{0}^{\pi}\frac{(\cos\theta)^{2n+4}}{1-4a^2\cos\theta}d\theta,\end{eqnarray*}$$ where the integral can be approximated by considering that the integrand function almost behaves like a normal distribution with zero mean, so: $$\sum_{k>(n+1)}a^{2k}\binom{2k}{k}=(2a)^{2n+4}\cdot \Theta\left(\frac{1}{\sqrt{n}}\right).$$ [Continues]