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.

I have to prove the following statement: $$ f(n) + g(n) \in \Omega(f(n)) $$

I am not sure what to do. Can I use this somehow?

$$ f(n) \in \Omega(g(n)) : \iff 0 \le lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} < \infty $$ Thank you in advance for any help!

share|improve this question
    
Maybe I don't understand your problem right. The title sounds as if the task is: If $f,g\colon \mathbb N\to\mathbb R$ are arbitrary functions (including the possibility that $f=g=0$!), then show that $f+g\in\Omega(f)$ or $f+g\in\Omega(g)$. Thus you do not have to show $f+g\in\Omega(f)$. Am I right? –  Hagen von Eitzen Oct 28 '12 at 17:38
add comment

1 Answer

up vote 1 down vote accepted

What you write as a condition for $f\in\Omega(g)$ isn't true. $f\in\Omega(g)$ if $f(n)\geq kg(n)$ for some $k$ and big enough $n$, so certainly for instance $n^3\in\Omega(n^2)$, but the limit of $n^3/n^2$ is $\infty$. I think you want $0<\lim f/g\leq\infty$.

With that change, this goes quickly: just write $$\lim_{n\to\infty} \frac{f(n)+g(n)}{f(n)}=\lim_{n\to\infty}1+\frac{g(n)}{f(n)}>0$$ To be precise, we might have the last limit be nonzero by not existing, rather than by being positive, as for instance if $f(n)=\langle 1,2,1,2,1...\rangle$ and $g(n)=\langle 2,1,2,1,...\rangle$. This would give $f+g=3$, and $3/f$ oscillates between $3$ and $3/2$ without converging. So your statement should really read $f+g\in\Omega(f)$ provided $\lim_{n\to\infty} (f+g)/f$ exists.

share|improve this answer
    
In any definition or proof based on the $\Omega$ class, one should avoid to assume that limits exist. This remark applies equally to the question itself, I know. –  Did Oct 28 '12 at 15:37
    
Thanks, I've added in the caveats. –  Kevin Carlson Oct 28 '12 at 16:03
    
That is not what I had in mind: the result holds even when $g/f$ does not converge. –  Did Oct 28 '12 at 16:25
add comment

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.