I have been struggling to lower bound the following expression
\begin{equation} f(N):= \frac{1}{N}\sum_{i=1}^N \frac{1}{2^N} \sum_{k=1}^{i} 2^{i-k} \binom{N+k-2}{k-1} , \end{equation}
with some simple formula, without the need of exactly calculating it. Does anyone have any suggestions?
- More precisely, one can go through it to re-write it as
\begin{align} f(N)=&\frac{1}{N}\sum_{i=1}^N \frac{1}{2^N} \sum_{k=1}^{i} 2^{i-k} \binom{N+k-2}{k-1} =\frac{1}{N}\sum_{i=1}^N \sum_{k=1}^{i}\frac{2^{i-k-N}}{(k-1)!}\prod_{j=0}^{k-2}(N+k-2-j)\\ &= \frac{1}{N}\sum_{i=1}^N \sum_{k=1}^{i}\frac{2^{i-k-N}}{(k-1)!}N^{k-1}+\frac{2^{-k-N}}{(k-1)!}N^{k-1}N^{k-2}+... \\ &= \frac{1}{N}\sum_{i=1}^N \frac{2^{1-i-N}}{(i-1)!}N^{i-1}+\frac{2^{-i-N}}{(i-3)!}\left(1+\frac{4}{(i-2)} \right)N^{i-2} + ... \\ &= \frac{2^{1-2N}}{(N-1)!}N^{N-2}+\frac{2^{2N}}{(N-3)!}\left(1+\frac{8}{(N-2)} \right)N^{N-3} + ... \end{align}
My goal is to lower bound these expressions with some straightforward expressions without precisely calculating them. Any idea will be more than welcome.
Thanks!