Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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
add comment

3 Answers 3

up vote 0 down vote accepted

$$\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}$.
share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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