2
$\begingroup$

I have proposed a classifier whose complexity can be written as

\begin{align*} \mathcal{O}\left(f(m)\right)&=\mathcal{O}\left(\log\left(\max_{x\in(0,1)}\left\{g(x,m)\right\}\right)\right)\\ g(x,m)&=\frac{(1+x)^m(1-x)}{1-x^{m+1}} \end{align*}

where $m\in\{0,1,2,3,...\},x\in(0,1)$.

There exist an evident upper bound for $g(x,m)$ but it is quite large:

\begin{align} (1+x)^m=\sum_{i=0}^m{\binom{m}{i}x^i}&<\binom{m}{{\lceil}\frac{m}{2}{\rceil}}\sum_{i=0}^{m}{}x^i\\ &<\binom{m}{{\lceil}\frac{m}{2}{\rceil}}\frac{1-x^{m+1}}{1-x} \end{align} \begin{equation} \longrightarrow \forall x: \frac{(1+x)^m(1-x)}{1-x^{m+1}}<\binom{m}{{\lceil}\frac{m}{2}{\rceil}} \end{equation} As you see $\binom{m}{{\lceil}\frac{m}{2}{\rceil}}$ is a generous upper bound.

Translating my question to Combinatorics language, I am seeking for a technique that provides the smallest or a small enough $U_m$ in the below formula. \begin{equation} \sum_{i=0}^m{\binom{m}{i}x^i}<U_m\sum_{i=0}^{m}{}x^i \end{equation} Can anyone provide any hint, please?

$\endgroup$
1
$\begingroup$

Hint. Note that the function $$f(x)=\frac{(1+x)^m(1-x)}{1-x^{m+1}}$$ is increasing in $(0,1)$ and $$\lim_{x\to 1^-} f(x)=\frac{2^m}{m+1}.$$

$\endgroup$
  • $\begingroup$ Thanks Robert!! $\endgroup$ – hossayni Mar 22 '18 at 8:57

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.