1

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!

davidlowryduda
  • 91,687
user46317
  • 155
  • 4
  • 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

1 Answers1

1

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.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
  • 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
  • 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