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))$
5
$\begingroup$
$\endgroup$
migrated from cstheory.stackexchange.com Aug 16 '12 at 21:29
This question came from our site for theoretical computer scientists and researchers in related fields.
-
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$
$\endgroup$
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.
-
$\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$
$\endgroup$
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}$.
2
$\begingroup$
$\endgroup$
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) = ?$, ...
-
$\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
