0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why not learn how to use MathJax? It is cool to be able to write mathematical expressions as you wish ;). And as a reader, I don't really like the "4n+1=4$^n$*4" part :/ $\endgroup$ – Scientifica Mar 8 '17 at 0:04
  • 1
    $\begingroup$ Ahh yes I am working on learning it! $\endgroup$ – agra94 Mar 8 '17 at 0:09
  • $\begingroup$ Ah ok cool then :) $\endgroup$ – Scientifica Mar 8 '17 at 6:54
3
$\begingroup$

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

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

since $3n \geq 1$.

$\endgroup$
  • $\begingroup$ 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^n*4 > n+1 and that, after simplification of 4^n*4, this completes our induction step? $\endgroup$ – agra94 Mar 8 '17 at 0:03
  • $\begingroup$ Yes, that's right. You follow the chain of inequalities down, so finally we have $4^{n+1}>n+1$, as required. $\endgroup$ – Nathan H. Mar 8 '17 at 0:05
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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 !

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.