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))$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityLet $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))$
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.
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}$.
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) = ?$, ...