# Inductive proof

• Oct 6th 2009, 09:43 AM
Jones
Inductive proof
Hai,

I need help with his one, it's pretty simple and im pretty darn lousy at math :)

Show that $(1+x)^n \geq 1 + nx$ for all positive integers n, and
all real numbers x $\geq 0$

It's true for $n=x=1$

But im stuck at the inductive step:
$(1+(x+1))^{n+1} \geq 1 + (n+1)(x+1)$

• Oct 6th 2009, 10:18 AM
Plato
Quote:

Originally Posted by Jones
Show that $(1+x)^n \geq 1 + nx$ for all positive integers n, and
all real numbers x $\geq 0$

It's true for $n=x=1$
But im stuck at the inductive step:
$(1+{\color{red}(x+1)})^{n+1} \geq 1 + (n+1)(x+1)$

You have a mistake in red above.
It should be $(1+x)^{n+1}=(1+x)^n(1+x)\ge (1+nx)(1+x)$
• Oct 6th 2009, 10:20 AM
Jones
Quote:

Originally Posted by Plato
You have a mistake in red above.
It should be $(1+x)^{n+1}=(1+x)^n(1+x)\ge (1+nx)(1+x)$

Why is it a misstake? Don't you have to apply the induction to all the real numbers as well?
• Oct 6th 2009, 10:25 AM
Plato
Quote:

Originally Posted by Jones
Don't you have to apply the induction to all the real numbers as well?

Absolutely not. The induction is only valid on the set of positive integers.
• Oct 6th 2009, 10:27 AM
Jones
Quote:

Originally Posted by Plato
Absolutely not. The induction is only valid on the set of positive integers.

Hm, have i missed something important here?

Why can't you apply induction on real numbers?
• Oct 6th 2009, 10:35 AM
Plato
Quote:

Originally Posted by Jones
Hm, have i missed something important here?
Why can't you apply induction on real numbers?

We prove that induction "works" by the use of the fact the positive integers are well ordered with respect $\le$.
That is, ‘every non-empty subset of positive integers contains a least element’.

But the real numbers are well ordered with respect $\le$.
The real number set $\{x:1 contains no least element.
• Oct 6th 2009, 11:24 AM
Jones
Quote:

Originally Posted by Plato
We prove that induction "works" by the use of the fact the positive integers are well ordered with respect $\le$.
That is, ‘every non-empty subset of positive integers contains a least element’.

But the real numbers are well ordered with respect $\le$.
The real number set $\{x:1 contains no least element.

Oh, i see, didn't know that..

Thanks for the clarification :)
• Oct 6th 2009, 11:25 AM
aman_cc
Quote:

Originally Posted by Plato
We prove that induction "works" by the use of the fact the positive integers are well ordered with respect $\le$.
That is, ‘every non-empty subset of positive integers contains a least element’.

But the real numbers are well ordered with respect $\le$.
The real number set $\{x:1 contains no least element.

What Plato said - is little more in a formal language with deeper concepts. If you are new to this maybe thinking like this will help

Why does induction work -
a. You prove it for 1.
b. You assume it for some 'n' and based on this assumption prove it will be true for 'n+1'

Now let's combine a and b above. Put n=1, by 'a' this is true for 1. Then by 'b' it is true for n+1(=2). Apply 'b' again and again. You see it is true for 1,2,3,4,5,...... You will 'generate' all the natural numbers by this procedure. Thus statement is true for all natural number.

Now think, will this work for real numbers? or even rationals? Can by repeatedly adding 1 (or any number) will you be able to list all the real numbers?

Hope it helps
• Oct 7th 2009, 01:36 PM
Jones
Quote:

Originally Posted by Plato
You have a mistake in red above.
It should be $(1+x)^{n+1}=(1+x)^n(1+x)\ge (1+nx)(1+x)$

Hi again, just one last question.

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

where did this last (x+1) come from?
• Oct 7th 2009, 02:05 PM
HallsofIvy
Because $a^{n+1}$ means $a^n(a)$!
• Oct 7th 2009, 02:09 PM
Plato
Quote:

Originally Posted by Jones
Hi again, just one last question.

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

where did this last (x+1) come from?

First it is not $(1+x)^{n+1} \ge 1+(n+1)x ({{x+1}})$
But it is $(1+x)^{n+1} \ge (1+nx) ({{x+1}})$
Because $(1+x)^{n+1}=(1+x)^n(1+x)$ law of exponents.
By the inductive hypothesis we know $(1+x)^n\ge (1+nx)$.