# Explicit Big-$\mathcal{O}$ proof with predicate logic

For my newest homework I have given two functions $h,h^+:\mathbb{N}\to\mathbb{R}$ with $h(n)=n^{(-1)^n}$ and $h^+(n)=h(n+1)$. I have to proove that $h^+(n) \not\in\mathcal{O}(h(n))$ with an explicit predicate formula. Here are my thoughts so far:

$$h(n)=n^{(-1)^n}=\begin{cases}\frac{1}{n}, &\text{ if }n=2k+1,\\\\n, &\text{ if }n=2k.\end{cases}$$ $$h^+(n)=(n+1)^{(-1)^{(n+1)}}=\begin{cases}\frac{1}{n+1}, &\text{ if }n=2k,\\\\n+1, &\text{ if }n=2k+1.\end{cases}$$

Assumption: $$h^+(n) \not\in\mathcal{O}(h(n))\Leftrightarrow (\forall c>0\;\forall n_0\in\mathbb{N}_0\;\exists n\geq n_0)\left[|h^+(n)|>c\cdot|h(n)|\right]\;.$$

The next step was to divide both cases with even and odd $n$, however the first equation drives me crazy: $$\frac{1}{n_0+1}>c\cdot n_0\text{, with }n_0=2k.$$

Now I fail at rearranging the upper equation to get an expression like this: $$n_0>\ldots\Rightarrow n(c):=\lceil\ldots\rceil +1\;.$$

How would you prove this and can you explain me why I am not able to solve this?

Thanks for any hint!

-

Notice that if $n$ is odd, $h^+(n)=n+1$, and $h(n)=1/n$, so $h^+(n)>n=n^2h(n)$. Thus, if $n\ge n_0$, $h^+(n)>n^2h(n)\ge n_0^2h(n)$. (Never mind for a moment what $n_0$ is; we’ll decide in a moment.)
Now suppose that $c>0$ is given. If you choose $n_0$ so that $n_0^2\ge c$, any odd $n\ge n_0$ will have the property that $h^+(n)>ch(n)$. (I didn’t bother with absolute values, since these functions are positive.) All you have to do to finish this up is specify just how to choose $n_0$, given $c$.