# Upper bound for $\sum_{j=0}^i {i \choose j}^{n}$

Is there an upper bound for sums of powers of binomial coefficients? I have $$\sum_{j=0}^i {i \choose j}^{n}$$

where $n$ is a positive integer.

I am hoping this will help me solve Limit for a double sum of binomials .

-
Crude upper bound: each term is bounded above by $i^n$, so their sum is bounded by $i^{n+1}$. –  vadim123 Dec 16 '13 at 17:09
How tight a bound do you want? You can get a full asymptotic expansion using Laplace's method... –  Igor Rivin Dec 16 '13 at 17:35
@IgorRivin My aim is to prove the limit math.stackexchange.com/questions/608296/… using this bound but I don't know exactly how tight it has to be for that. –  user115998 Dec 16 '13 at 17:51

See central binomial coefficient. $$\sum<(i+1)\bigg[2^i\sqrt\frac2{i\pi}\bigg(1-\frac1{4i}\bigg)\bigg]^n$$

-
You mean bound it by $(i+1)2^{in}/i^{n/2}$? –  user115998 Dec 16 '13 at 17:12
I think there's a small typo in your formula, and I also think you should use the last one, which provides the best accuracy, but yeah, that's pretty much the idea. –  Lucian Dec 16 '13 at 17:39
Thank you. Numerically it seems this is tight enough for my limit problem. I still don't know how to prove it however. –  user115998 Dec 16 '13 at 21:25
Should that be $1/8i$ instead of $1/4i$ ? –  user115998 Dec 16 '13 at 22:00
$i=2n\iff4i=8n$ –  Lucian Dec 16 '13 at 22:07

If $x,y \in \mathbb{Z}$ where $x,y \geq 0$, then $x^n + y^n \leq (x + y)^n$ for any $n \geq 1$.

By induction, we can show $\sum_{j = 0}^{i} C(i,j)^n \leq \Big(\sum_{j = 0}^{i} C(i,j)\Big)^n = (2^i - 1)^n$.

The bound is a tad crude, though.

-
Thanks. The problem is that I think that is too loose to prove the limit I need. –  user115998 Dec 16 '13 at 17:21