Not following what's happening with the exponents in this proof by mathematical induction.

Question

I'm not understanding what's happening in this proof. I understand induction, but not why $2^{k+1}=2*2^{k}$, and how that then equals $k^{2}+k^{2}$. Actually, I really don't follow any of the induction step - what's going on with that algebra? Thanks!

Let $P(n)$ be the statement

$2^n > n^2$, if $n$ is an integer greater than 4.

Basis step:

$~~~~~P(5)$ is true because $2^5 = 32 > 5^2 = 25$

Inductive step:

$~~~~~~$Assume that $P(k)$ is true, i.e. $2^k > k^2$. We have to prove that $P(k+1)$ is true. Now $$\begin{aligned} 2^{k+1} & = 2 \cdot 2^k\\ & > 2 \cdot k^2\\ & = k^2 + k^2\\ & > k^2 + 4k\\ & \geq k^2 +2k+1\\ & = (k+1)^2 \end{aligned}$$ $~~~~~$ because $k>4$

$~~~~~$ Therfore $P(k+1)$ is true

Hence from the principle of mathematical induction the given statement is true.

Answer 1

I have copied the induction step table format from your question and will reformat it as I had to do in my high school geometry class. I find it very helpful to get away from the table as you gave it.

Set $P(n)$ equal to the statement that 2^n>n^2 for all n>4. Note the basis step 2^4>4^2 is true.

$~~~~~~$Assume that $P(k)$ is true, i.e. $2^k > k^2$. We have to prove that $P(k+1)$ is true. Now

\begin{array}[10,2]{} STATEMENT & REASON \\ 2^{k+1} = 2 \cdot 2^k & \text{Induction step of the definition of }2^n \\ 2^k > k^2 & \text{This is the induction hypothesis.} \\ 2 \cdot 2^k > 2 \cdot k^2= k^2 + k^2 & \text{Multiplying by a positive number preserves inequalities} \\ & \text{ and the distributive law.} \\ k^2 + k^2 > k^2 + 4k & k>4\text{ by hypothesis, so } k^2 >4k \text{ and then } k^2 + 4k > k^2 + 2k +2\\ & \text{and the standard rules of inequalities used above apply.} \\ k^2 + 4k \geq k^2 +2k+1 & 4k > 2k+1 \text{ since }2k-1>0 \\ k^2 +4k +1 =(k+1)^2 & \text{Multiplication distributes over addition.} \\ \end{array} $~~~~~~$ This shows $P(k)\implies P(k+1)$, and the principle of finite induction completes the proof that $P(n)$ is true for all $n>4$ .

Answer 2

Perhaps writing shortly a justification for each step can help. Let us denote

$$\begin{align*}&2^k>k^2=\color{red}{I.H.} =\text{ Inductive Hypothesis. This is what you assume after showing for k = 5}\\&k^2=k\cdot k>4k=\color{blue}{B.A.}=\text{Basic Assumption. From here we start}\\&4k\ge 2k+1=\color{green}{S.A.}=\text{Simple Algebra:}\;\;4k\ge 2k+1\Longleftrightarrow 2k\ge 1\end{align*}$$

So now your proof can look as follows:

$$2^{k+1}\stackrel{\text{exponents law}}=2\cdot 2^k\stackrel{\color{red}{I.H.}}>2\cdot k^2=k^2+k^2\stackrel{\color{blue}{B.A.}}>k^2+4k\stackrel{\color{green}{S.A.}}\ge k^2+2k+1=(k+1)^2$$

Answer 3

You ask two questions:

(1) By definition, $$2^{k+1} = \underbrace{2 \quad \textrm{...} \quad 2}_{\textrm{ (k+1 times)}} = 2 \cdot \underbrace{2 \quad \textrm{...} \quad 2}_{\textrm{ (k times)}} = 2 \cdot 2^k.$$ As others have pointed, it's the usual rule to calculate an exponential: $a^x \cdot a^y = a^{x+y}$.

(2) The step immediately before $k^2 + k^2$ is that it equal $2k^2$. I assume that is clear (?) - you obviously always have $2a = a+a$. These two are equal; they are not equal to $2 \cdot 2^k$ (as you write, but probably don't mean). So I assume you ask why is the step before true, the one going $2 \cdot 2^k > 2 \cdot k^2$. This is using the induction assumption, assumed to be true for $k$ (as you write yourself earlier in "Let P(n) be the statement..."): if $2^k > k^2$, then obviously also $2 \cdot 2^k > 2 \cdot k^2$

Answer 4

The arithmetic has already been explained, but not the intuition motivating the induction. We desire to prove by induction that the function $\rm\ \color{#C00}{2^n - n^2 =\, f(n)}\,$ is positive for $\rm\:n \ge 5.\:$ Notice

$$\begin{eqnarray}\rm f(n\!+\!1) &=&\rm\ 2\cdot \color{#C00}{2^n} - (n\!+\!1)^2 =\, 2\,(\color{#C00}{f(n)+n^2})-(n\!+\!1)^2\\ \rm \Rightarrow\ \ f(n\!+\!1) &=&\rm\ 2\: f(n) + (n\!-\!1)^2\! - 2\end{eqnarray}$$

Now the induction step is clear: $\rm\ f(n)> 0\,\Rightarrow\, f(n\!+\!1) > 0\,$ since $\rm\,f(n\!+\!1)\,$ is a sum of terms $\,> 0,$ namely, the first rhs summand $\rm\,2\,f(n)>0\:$ since $\rm\:f(n)>0\:$ by the induction hypothesis; $ $ further, the second rhs summand $\rm\:(n\!-\!1)^2\!-2 > 0\:$ for $\rm\:n \ge 3\ $ (by $\rm\,x^2\,$ is increasing, or by induction).

More generally one can easily prove by induction that if a function on $\,\Bbb N\,$ satisfies a recurrence of the form $\rm\: f(n\!+\!1) =\, a(n)\, f(n) + b(n)\:$ and $\rm\,f(n_0)> 0\:$ then $\rm\,f\,$ remains positive for all $\rm\:n \ge n_0,\:$ assuming that both $\rm\:a(n)>0\,$ and $\rm\,b(n) > 0$ for $\rm\:n > n_0.\:$ It's really nothing more than the obvious induction that an increasing function stays larger than its initial value, which amount essentially to iterating the transitivity law for inequalities $\rm\:f_{n+1} > f_n > \cdots > f_{0}\:\Rightarrow\: f_{n+1} > f_{0}.$

Many induction proofs can be cast in this form. For example, products and exponentials of polynomials satisfy such recurrences. The method often succeeds because it replaces hairy exponential arithmetic by much simpler polynomial arithmetic (verifying positivity of the polynomials $\rm\:a(n),b(n),\:$ which requires no insight since there is a simple algorithm).

This is a simple generalization of telescopy - about which much has been written here.