0

I will prove by induction the statement $P(k)$: "For all $k\in\mathbb{N},4^k>k$."

The base case $P(1)$ results in $4>1$ which is a true statement.

Thus, I assume $P(n)$ to be true and consider $P(n+1)$.

$$4^{n+1} = 4^n \cdot 4 > 4n$$

I know that I am then supposed to rewrite $4n$ as $3n+n$. However, I do not know where to proceed from after that. According to my professor, I am suppoed to wind up with $3n+n=n+1$. However, I do not know where this comes from. Any help would be appreciated.

John
  • 1,019
jmoore00
  • 619

4 Answers4

3

You kind of just have to play with inequalities a bit.

$$ 4n = 3n + n \geq 1 + n $$

since $3n \geq 1$.

Nathan H.
  • 694
  • Interesting. So with this type of problem, the goal isn't really trying to make 3n+n equal to n+1 but more about showing how because 3n+n > n+1, that the above inequality is still satisfied? So, because 4^n * 4 > 3n+1 > n+1, that 4^n4 > n+1 and that, after simplification of 4^n4, this completes our induction step? – jmoore00 Mar 08 '17 at 00:03
  • Yes, that's right. You follow the chain of inequalities down, so finally we have $4^{n+1}>n+1$, as required. – Nathan H. Mar 08 '17 at 00:05
0

You can use the fact that: $$4^k=(1+3)^k\geq 1+3k> k$$

0

Your claim is false! You have to reformulate the inductive step in order to be able to apply the inductive hypothesis, I.e. $4^k > k$. This can be done rewriting the inductive step

$4^{k+1} =4 \cdot 4^k$

And now you know the right hand side of the equality is greater then $4 \cdot k$, that is obviously greater then $k+1$ for $ k \ge 1$ and then you win !

Erik Pillon
  • 187
0

A stronger result, $2^k>k$, is the finite-set case of Cantor's theorem. So a proof without induction is also possible.

J.G.
  • 115,835