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

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.

-
Minor detail: as you wrote it, the basis step would be $P(0)$ or $P(1)$ (depending on wether you let $0\in \mathbb{N}$ or not), and in either case if would be logically trivially true. – Git Gud Jan 29 '13 at 19:08
Do you know what $2^n$ means? Why are you asking about $2\cdot 2^k$ equaling $k^2+k^2$ when the proof doesn't assert this? – Chris Eagle Jan 29 '13 at 19:08
Hints: $2^{k+1}$ can be written as $2^{k} 2^{1}$. Also, reread the next step where you are confused as he is making a mathematical argument regarding the size of the numbers and you are reading it incorrectly - look again. Regards – Amzoti Jan 29 '13 at 19:09
@GitGud: the $n=4$ case is false, so starting before that is foolish. – Chris Eagle Jan 29 '13 at 19:09
@ChrisEagle He said the statement $P(n)$ is $$n>4 \Longrightarrow 2^n>n^2$$ That's the statement, period. If you start with $5$ you're proving something different. Equivalent, but different. – Git Gud Jan 29 '13 at 19:11

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

-
I suspect that the major problem with your understanding is in the way you wrote down the equalities and inequalities. None of them were on the same line except for the first. All of these steps are the usual operations of arithmetic and inequalities plus the induction hypothesis. – Barbara Osofsky Jan 29 '13 at 21:42

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

-
+1 I prefer this colored one. – Babak S. Jan 30 '13 at 12:27

(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$

-

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.

-