Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.