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?
 A: 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.
A: $$\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:


*

*I wrote down the expression for $f(k+1)$.

*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$.

*We also know that $k+1 > 2$ which implies that $(k+1) 2^k >2 \cdot 2^k$.

*$2 \cdot 2^k = 2^{k+1}$. So it follows that $f(k+1)>2^{k+1}$.

A: 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.
