11
$\begingroup$

So:

$ (1+x)^n ≥ 1 + nx $

So he checks for 1, and get:

$ 1+x ≥ 1+x $

Next for variable k:

$ (1+x)^k ≥ 1 + kx $

Then the book wanna prove:

$ (1+x)^{k+1} ≥ 1 + (k + 1)x $

And here is books proof:

$ (1+x)^{k+1} = (1+x)^k (1+x) ≥ (1+kx)(1+x) $ $ = 1+(k+1)x + kx^2 ≥ 1 + (k + 1)x $

Finished! Well... How did the book get this: $(1+kx)(1+x)$ in that last part? Sorry, I'm so confused. Sorry if this to easy to be here. Thanks for all help helping me understand it!

2 Answers 2

11

Your question is a great one, it is most welcome here! The answer is that, in a proof by induction, we first check the base case (here, it is $n=1$), and then, assuming the result is true for $n=k$, we prove that the result must also be true for $n=k+1$. In other words, we want to prove that $\text{true for }n=k\implies\text{true for }n=k+1$

Intuitively, this lets us say $\begin{align} (\text{base case}) \qquad\qquad\qquad\qquad\qquad\qquad&\text{true for }n=1\qquad\checkmark\\ {\text{true for }n=1,\text{ and }\atop (\text{true for }n=k\implies\text{ true for }n=k+1)}\bigg\}\implies&\text{true for }n=2\qquad\checkmark\\ {\text{true for }n=2,\text{ and }\atop (\text{true for }n=k\implies\text{ true for }n=k+1)}\bigg\}\implies&\text{true for }n=3\qquad\checkmark\\ \vdots\end{align}$

Thus, when we try to prove that the statement is true for $n=k+1$, i.e. $(1+x)^{k+1} ≥ 1 + (k + 1)x,$ we can use the assumption that the statement is true for $n=k$, i.e. $(1+x)^k ≥ 1 + kx.$ The reason why we have $(1+x)^k (1+x) ≥ (1+kx)(1+x)$ is that we are assuming $(1+x)^k ≥ 1 + kx$ is true, and then we multiply both sides by $(1+x)$.

  • 0
    Actually, $n=0$ can be a base case as well :-)2011-08-21
3

In your next to last line, you have $(1+x)^k,$ which you have assumed two lines above is greater than or equal to $1+kx$. So it made the substitution, using a $\ge$ sign. You might look at this answer, which has a detailed explanation of induction.