# proof by induction

• Feb 21st 2010, 08:56 PM
surjective
proof by induction
Hello,

Could someone help me prooving the following:

If

\$\displaystyle x+1 >= 0 \$

then

\$\displaystyle (1+x)^n >= 1+nx\$

for all natural numbers.

I hope that i have written everything correctly (this is my first time).

NB! How do i type in equations and stuff?

Thank you very much.
• Feb 21st 2010, 09:29 PM
o_O
Please no double posting. On typing math symbols, see this thread for more: LaTex Tutorial

You can see the code that generates the image by clicking on it.

As for your problem, let's look at the inductive step. Assuming that \$\displaystyle \color{red} (1+x)^k \geq 1 + kx\$, our goal is to prove that \$\displaystyle (1+x)^{k+1} \geq 1 + (k+1)x\$.

Looking at the LHS, notice that: \$\displaystyle (1+x)^{k+1} = {\color{red}(1+x)^k}(1+x)\$

Now I highlighted the part in red for a reason .. and it shouldn't be too hard to show that this is bigger than \$\displaystyle 1 + (k+1)x\$.
• Feb 22nd 2010, 12:30 AM
surjective
Proof by induction
Hello again,

Sorry for the inconvenience. The thing is that what you mentioned before is exactly what I have already done . . . and then I get stuck. I can't seem to get the "great idea" (maybe because I havn't slept all night).

What I'm trying to do is to reach the conslusion (instead of showing the truthfulness of an inequality):

\$\displaystyle (1+x)^{n+1} \geq 1+(n+1)x \$

Now from calculus I know that:

\$\displaystyle (1+x)^{n+1}= (1+x)^{n}(1+x) \$

Using the inductive step we may write:

\$\displaystyle (1+x)^{n}(1+x) \geq (1+nx)(1+x) \$

This is where I get stuck.

Thanks.
• Feb 22nd 2010, 03:21 AM
Quote:

Originally Posted by surjective
Hello again,

Sorry for the inconvenience. The thing is that what you mentioned before is exactly what I have already done . . . and then I get stuck. I can't seem to get the "great idea" (maybe because I havn't slept all night).

What I'm trying to do is to reach the conslusion (instead of showing the truthfulness of an inequality):

\$\displaystyle (1+x)^{n+1} \geq 1+(n+1)x \$

Now from calculus I know that:

\$\displaystyle (1+x)^{n+1}= (1+x)^{n}(1+x) \$

Using the inductive step we may write:

\$\displaystyle (1+x)^{n}(1+x) \geq (1+nx)(1+x) \$

This is where I get stuck.

Thanks.

Continuing on,

if \$\displaystyle (1+x)^n\ \ge\ 1+nx,\$ then the following must be true

\$\displaystyle (1+x)^{n+1}\ \ge\ 1+(n+1)x\$

Proof

\$\displaystyle (1+x)^n(1+x)\ \ge\ (1+nx)(1+x)\$ if the first statement is true

\$\displaystyle (1+x)^n(1+x)\ \ge\ 1+x+nx+nx^2\$

\$\displaystyle (1+x)^{n+1}\ \ge\ [1+(n+1)x]+nx^2\$

This means that if \$\displaystyle (1+x)^n\ \ge\ 1+nx\$

then \$\displaystyle (1+x)^{n+1}\ \ge\ [1+(n+1)x]+nx^2\$

and therefore

\$\displaystyle (1+x)^{n+1}\ \ge\ 1+(n+1)x\$ definately.

That's the inductive step.
• Feb 22nd 2010, 04:18 AM
surjective
Proof by induction
Hello,

Thank you very much. It seems that I was only one step away from completing the proof. Thank you all very much.