5
$\begingroup$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds:

$\qquad f(n+1) = \Theta(f(n))$

$\endgroup$
  • 7
    $\begingroup$ Hint: think about the gamma function. $\endgroup$ – Huck Bennett Aug 16 '12 at 19:10
  • 1
    $\begingroup$ Do you know the definition of $\Theta$? You just want to show that $f(n+1) \in O(f(n))$ and $f(n+1) \in \Omega (f(n))$, or just provide a counter example. Also, are you sure that it's $f(n+1)$ and not $f(n)+1$? $f(n+1)$ is a real number, not a function, and $\Theta$ represents a set of functions. $\endgroup$ – jmite Aug 16 '12 at 21:35
  • $\begingroup$ What have you tried? $\endgroup$ – Raphael Aug 16 '12 at 22:48
  • 1
    $\begingroup$ Let $f(n) = 2^{2^n}$, now check your statement. $\endgroup$ – user742 Aug 18 '12 at 11:15
6
$\begingroup$

Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.

$\endgroup$
  • $\begingroup$ Thanks a lot. I was expecting simple answer like this! It helped me a lot. Also, I got some idea on how to think on these type of problems. I appreciate it sincerely. $\endgroup$ – aghost Aug 17 '12 at 17:00
  • $\begingroup$ @AnirbanGhosh Glad it helped you understand! If this makes sense, take a look at Kaveh's answer as well... it's more abstract, but more general, and uses the same principle in a more generic way. Sort of a quick way of stating it would be "if you need a continuous function, pick a discrete one that works, then connect the dots". $\endgroup$ – Patrick87 Aug 17 '12 at 17:01
3
$\begingroup$

Hint:

First consider a function $f:\mathbb{Z} \to \mathbb{Z}$ like

$$f(n) = \begin{cases} g(k) & \text{if } n=2k\in \mathbb{Z} \\ h(k) & \text{if } n=2k+1\in \mathbb{Z} \\ \end{cases}$$

Then extend it in a continuous way to a function over $\mathbb{R}$.

$\endgroup$
2
$\begingroup$

I read your question like this. Given such a function $f$, define $g(n) = f(n)$ and $g'(n) = f(n+1)$. Is $g' \in \Theta(g)$?

Hint 1: If this is true, for all such functions $f$ you have a $c$ such that $f(n+1) \leq c f(n)$ for all sufficiently large $n$ (by definition).

Hint 2: $f(n+1) \leq c f(n) \iff f(n+1) - f(n) \leq (c-1)f(n)$ -- does that trigger some high school maths knowledge?

Ultimate hint:

For $f_1(n) = n$, $f_1(n+1)-f_1(n) = 1$.
For $f_2(n) = 2^n$, $f_2(n+1) - f_2(n) = f_2(n)$.
For $f_3(n) = ?$, ...

$\endgroup$
  • $\begingroup$ I don't understand your examples. For $f(n) = n$ and $g(n) = 2^n$ we have that $f(n) \in \Theta(f(n+1))$ and $g(n) \in \Theta(g(n+1))$ respectively. $\endgroup$ – Huck Bennett Aug 17 '12 at 0:52
  • $\begingroup$ I am sorry to say I am not able to proceed in either direction. I tried to come up with a counterexample but failed. Also I tried to prove it, again I have failed. So, which direction is the correct approach - prove or disprove. Also, I am sorry to say I could not make out anything from the above replies. My limitation may be. $\endgroup$ – aghost Aug 17 '12 at 1:50
  • $\begingroup$ @HuckBennett: They are hints, not solutions on their own. $\endgroup$ – Raphael Aug 17 '12 at 5:59
  • $\begingroup$ @AnirbanGhosh: Your question is very thin, so I won't give you a full answer. One more hint: try to continue the sequence of functions $f$ I started in the spoiler. $\endgroup$ – Raphael Aug 17 '12 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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