4
$\begingroup$

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?

  • 0
    I'm confused about the step where we add one. $P(n) \implies p(n+1)$2011-03-09

3 Answers 3

0

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.

3

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.

0

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