1
$\begingroup$

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!

  • 0
    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?2012-10-28

1 Answers 1

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.

  • 0
    That is not what I had in mind: the result holds even when $g/f$ does not converge.2012-10-28