# Asymptotic growth rate of $f(n)$ and $f(n+1)$

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))$

• Hint: think about the gamma function. – Huck Bennett Aug 16 '12 at 19:10
• 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. – jmite Aug 16 '12 at 21:35
• What have you tried? – Raphael Aug 16 '12 at 22:48
• Let $f(n) = 2^{2^n}$, now check your statement. – user742 Aug 18 '12 at 11:15

## 3 Answers

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.

• 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. – aghost Aug 17 '12 at 17:00
• @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". – Patrick87 Aug 17 '12 at 17:01

### 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}$.

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) = ?$, ...

• 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. – Huck Bennett Aug 17 '12 at 0:52
• 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. – aghost Aug 17 '12 at 1:50
• @HuckBennett: They are hints, not solutions on their own. – Raphael Aug 17 '12 at 5:59
• @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. – Raphael Aug 17 '12 at 6:01