# If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$

I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question.

Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$.

Use induction to prove that $f(n) > 2^n$ for all $n>2$.

Note that $f(1) =2$, $f(2)=4$. I understand the basis step, so I'm not going to write that out.

Now we have. $f(k) = k \cdot f(k-1)> 2^k$ we want to show the following.

$f(k) + f(k+1) = (k+1)\cdot f(k)> 2^{k+1}$ This is where I'm getting stuck. Can someone give me a hint as to how to proceed?

• $f(k)>2^k$ and $k+1>2$, therefore $2^{k+1}=2^k\times 2<f(k)\times 2<f(k)\times (k+1)=f(k+1)$ – Asaf Karagila Mar 9 '11 at 6:44
• In the inductive step, you assume that $f(k)\gt 2^k$; you want to prove that $f(k+1)\gt 2^{k+1}$. I don't know why you have "$f(k)+f(k+1)$". – Arturo Magidin Mar 9 '11 at 6:44
• Your inductive step should be $f(k)=k\cdot f(k-1)\ge k\cdot 2^{n-1}$ – Ross Millikan Mar 9 '11 at 6:49
• I'm confused about the step where we add one. $P(n) \implies p(n+1)$ – lampShade Mar 9 '11 at 6:57

\begin{align} P(3):&\quad f(3)=12 > 8 = 2^3 \\ P(k):&\quad f(k)>2^k \\ P(k+1):&\quad f(k+1) = (k+1)f(k) > (k+1) 2^k >2 \cdot 2^k = 2^{k+1} \end{align}

So what we do is first to show that $f(n)>2^n$ for $n=3$. Then we assume that it is also true for $n=k$. At last we prove that it is true for $k+1$ if it is true for $k$.

What I did in the last step is this:

1. I wrote down the expression for $f(k+1)$.
2. Because of the step $P(k)$ we know (assume) that $f(k)>2^k$ which implies that $(k+1)f(k) > (k+1) 2^k$ since $k+1>0$.
3. We also know that $k+1 > 2$ which implies that $(k+1) 2^k >2 \cdot 2^k$.
4. $2 \cdot 2^k = 2^{k+1}$. So it follows that $f(k+1)>2^{k+1}$.

HINT $\rm\quad\displaystyle \frac{f(n)}{2^n}\ =\ \frac{2}2\ \frac{2}{2}\ \frac{3}2\ \frac{4}2\ \cdots\ \frac{n}2\ > 1\$ for $\rm\ n > 2\$ since each factor is $>1$ after the 2nd factor.

Generally that works to show that factorials grow faster than powers, i.e. $\rm\ f(n) > c^n\$ for $\rm\ n > n_0\:.\$ It suffices to show: eventually $\rm\ g(n) = f(n)/c^n > 1\:,\:$ or, equivalently, eventually $\rm\: g(n+1)/g(n) > 1 \$ since, by multiplicative telescopy, $\rm\:g(n)\:$ is a product of these adjacent term ratios, namely

$$\rm g(0)\ \ \prod_{k\:=\:0}^{n-1}\ \frac{g(k+1)}{g(k)}\ = \ \ {\rlap{--}g(0)}\frac{\rlap{--}g(1)}{\rlap{--}g(0)}\frac{\rlap{--}g(2)}{\rlap{--}g(1)}\ \ \cdots\ \ \frac{g(n)}{\rlap{----}g(n-1)}\ =\ \ g(n)$$

Yours has $\rm\ g(k+1)/g(k)\ =\ (k+1)/2\ >\ 1\$ for $\rm\ k > 1\$ so $\rm\:g(n) > 1\:,\:$ as a product of terms $> 1\:.$

As I have emphasized here before in many posts, by means of cancelling complicated expressions, telescopy often reduces induction problems to trivialities (e.g. a product of terms $> 1$ is itself $> 1$). Difficult problems involving hyperrational functions (i.e. $\rm\ f(n+1)/f(n) =$ rational function of $\rm\:n\:,\:$ such as powers and exponentials) are, after application of telescopy, greatly simplified to trivial problems about rational functions - functions so simple that questions about such can be decided mechanically by algorithms.

It might be clearer if you wrote $f(3)=12>8$ as well, to start you off.

Now with the inductive hypothesis $f(n)>2^n$ and $n>2$ you look at $f(n+1)$ and this implies $$f(n+1) = n \times f(n) > n \times 2^n > 2 \times 2^n = 2^{n+1} \textrm{ and } n+1>n>2$$ (essentially what Asaf Karagila wrote backwards), i.e. $$f(n+1) > 2^{n+1} \textrm{ and } n+1>2$$ which is all you need.