0
$\begingroup$

Apologies for a second question on induction. I've been strongly advised to learn to write induction proofs in a standard way, not like this. That seems fair enough. Are the below proofs very clear and easy to follow? Is the formatting standard? Most importantly, are there any mathematical errors?

Do you need to justify statements such as $2^k/k > 2 + 1/k, \ k \geq 3$? If so, where would you slip in a statement such as "LHS constantly increases, RHS constantly decreases" without breaking up the formatting of the proof?

Please feel free to copy these and answer with any adjustments you would make.


$\underline{Proof. \ \ 2^n > n^2 \ \text{ for } \ n \geq 5}$

$2^n>n^2$ is true for $n=5$: \begin{align*} 2^5 &> 5^2 \\ 32 &> 25 \end{align*} If $2^n>n^2$ is true for $n=k$: \begin{align*} 2^k &> k^2 \tag{IH} \end{align*} Then $2^n>n^2$ is true for $n=k+1$: \begin{align*} 2^k/k &> 2+1/k \tag{true for $k\geq3$} \\ 2^k &> 2k+1 \\ 2^k + 2^k &> k^2+2k+1 \tag{using IH} \\ 2 \cdot 2^k &> k^2+2k+1 \\ 2^{k+1} &> (k+1)^2 \\ \end{align*} $\therefore$ By the axiom of induction, $2^n > n^2 \ \ \square$


$\underline{Proof. \ \ 2^n > 2n + 1 \ \text{ for } \ n > 2}$

$2^n > 2n + 1$ is true for $n=3$: \begin{align*} 2^3 &> 2 \cdot 3 + 1 \\ 8 &> 7 \end{align*} If $2^n > 2n + 1$ is true for $n=k$: \begin{align*} 2^k &> 2k + 1 \tag{IH} \end{align*} Then $2^n > 2n + 1$ is true for $n=k+1$: \begin{align*} 2^k &> 2 \tag{true for $k>1$} \\ 2^k + 2^k &> 2k + 3 \tag{using IH} \\ 2 \cdot 2^k &> 2k + 3 \\ 2^{k+1} &> 2(k+1) + 1 \\ \end{align*} $\therefore$ By the axiom of induction, $2^n > 2n + 1 \ \ \square$

$\endgroup$
1
1
$\begingroup$

For the induction step I would write $$2^{k+1} > 2k^2 = k^2 + k^2 = k^2 + 2k + (k-2)k $$ $$> k^2 + 2k + 1 = (k+1)^2.$$

This way I use $2^k > k^2$ multiplied by two to get the lhs for $k+1$ then show that the inequality holds for the $k+1$ rhs.

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