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?

  • $\begingroup$ $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)$ $\endgroup$ – Asaf Karagila Mar 9 '11 at 6:44
  • $\begingroup$ 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)$". $\endgroup$ – Arturo Magidin Mar 9 '11 at 6:44
  • $\begingroup$ Your inductive step should be $f(k)=k\cdot f(k-1)\ge k\cdot 2^{n-1}$ $\endgroup$ – Ross Millikan Mar 9 '11 at 6:49
  • $\begingroup$ I'm confused about the step where we add one. $P(n) \implies p(n+1)$ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.