Induction proof

**justchillin** · August 14th, 2009, 08:02 AM

I'm just trying to learn induction from scratch and my book asks me to proof the generalized version of the triangle inequality.

If $a_{1},a_{2},...,a_{n}$ are arbitrary real numbers, then

$|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

My solution is as follows:
Let $P_{n}$ be the preposition that $|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

$P_{1}$ and $P_{2}$ are true. $P_{2}$ is the normal triangle inequality, so i assume i don't need to show that it is true.

With the induction hypothesis i assume that $P_{n}$ is true.

Setting
$|a_{1}+a_{2}+ ...+a_{n}| = S_{1}$
$|a_{1}| + |a_{2}| +...+ |a_{n}|= S_{2}$
$|S_{1}| \leq S_{2}$
So

We are trying to show that
$|S_{1} +a_{n+1}| \leq |S_{2}| + |a_{n+1}|$

Using cases
1) $S_{1} \geq 0$ and $a_{n+1} \geq 0$

$|S_{1} +a_{n+1}|= S_{1} +a_{n+1} \leq S_{2} +a_{n+1}$ this is true because $|S_{1}| \leq S_{2}$ according to the induction hypothesis. Also according to the transitive property of real numbers if a< b, then a+c < b+c.

2) $S_{1} < 0$ and $a_{n+1} \geq 0$

$|S_{1} +a_{n+1}| \leq S_{2} +|a_{n+1}|$

Since $|S_{1}| \leq S_{2}$ is true then $|S_{1} +a_{n+1}| \leq |S_{1}| + |a_{n+1}| \leq S_{2} +|a_{n+1}|<br />$

3 $S_{1} < 0$ and $a_{n+1} < 0$

$|S_{1} +a_{n+1}| \leq|S_{1} |+|a_{n+1}|\leq S_{2} +|a_{n+1}|$

Therefore it is true that $|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

Is my proof correct ?
And is there a better way of doing this?

**ynj** · August 14th, 2009, 08:17 AM

n=2
(|a1|+|a2|)^2=a1^2+a2^2+2|a1||a2|>=a1^2+a2^2+2a1a2 =(a1+a2)^2
thus |a1+a2|<=|a1|+|a2|
suppose for k<n it is true
then
|a1+....an|<=|a1+....an-1|+|an|
by induction |a1+...an-1|<=|a1|+...|an-1|
so |a1+...an|<=|a1|+..|an|

**justchillin** · August 14th, 2009, 08:21 AM

If $a_{i}\geq 0$ and $i \geq 1$ then

$(1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}$

My solution:

Let $P_{n} = (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}<br />$ ofcourse $P_{1}$ and $P_{2}$ are true.

According to the induction hypothesis, we assume $P_{n}$ is true.

Let $(1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n})= \rho$

and
$1+a_{1} + a_{2}+...+ a_{n} = S$

We have $\rho \geq S$

Okay moving on ...

We have to show this is true and $P_{n} implies P_{n+1}$
$\rho \cdot(1+ a_{n+1} )\geq S + a_{n+1}$

Doing some algebra we get

$\rho \geq S + a_{n+1}(1-\rho)$ which is true because $(1-\rho)\leq 0$ and $\rho \geq S$ and $a_{n+1}\geq 0$

Is this proof correct and is there a more clever way of doing this É

Originally Posted by ynj

n=2
(|a1|+|a2|)^2=a1^2+a2^2+2|a1||a2|>=a1^2+a2^2+2a1a2 =(a1+a2)^2
thus |a1+a2|<=|a1|+|a2|
suppose for k<n it is true
then
|a1+....an|<=|a1+....an-1|+|an|
by induction |a1+...an-1|<=|a1|+...|an-1|
so |a1+...an|<=|a1|+..|an|

Thanks a lot this is a more clever way of doing it. Thanks again.

But is my way correct É ( My keyboard is acting up)

**ynj** · August 14th, 2009, 08:30 AM

Originally Posted by justchillin

I'm just trying to learn induction from scratch and my book asks me to proof the generalized version of the triangle inequality.

If $a_{1},a_{2},...,a_{n}$ are arbitrary real numbers, then

$|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

My solution is as follows:
Let $P_{n}$ be the preposition that $|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

$P_{1}$ and $P_{2}$ are true. $P_{2}$ is the normal triangle inequality, so i assume i don't need to show that it is true.

With the induction hypothesis i assume that $P_{n}$ is true.

Setting
$|a_{1}+a_{2}+ ...+a_{n}| = S_{1}$
$|a_{1}| + |a_{2}| +...+ |a_{n}|= S_{2}$
$|S_{1}| \leq S_{2}$
So

We are trying to show that
$|S_{1} +a_{n+1}| \leq |S_{2}| + |a_{n+1}|$

Using cases
1) $S_{1} \geq 0$ and $a_{n+1} \geq 0$

$|S_{1} +a_{n+1}|= S_{1} +a_{n+1} \leq S_{2} +a_{n+1}$ this is true because $|S_{1}| \leq S_{2}$ according to the induction hypothesis. Also according to the transitive property of real numbers if a< b, then a+c < b+c.

2) $S_{1} < 0$ and $a_{n+1} \geq 0$

$|S_{1} +a_{n+1}| \leq S_{2} +|a_{n+1}|$

Since $|S_{1}| \leq S_{2}$ is true then $|S_{1} +a_{n+1}| \leq |S_{1}| + |a_{n+1}| \leq S_{2} +|a_{n+1}|<br />$

3 $S_{1} < 0$ and $a_{n+1} < 0$

$|S_{1} +a_{n+1}| \leq|S_{1} |+|a_{n+1}|\leq S_{2} +|a_{n+1}|$

Therefore it is true that $|a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.$

Is my proof correct ?
And is there a better way of doing this?

I think it is correct..

**justchillin** · August 14th, 2009, 08:33 AM

What about the second one É ( my keyboard doesnèt want to produce punnctuations.)

**ynj** · August 14th, 2009, 08:34 AM

Originally Posted by justchillin

If $a_{i}\geq 0$ and $i \geq 1$ then

$(1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}$

My solution:

Let $P_{n} = (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}<br />$ ofcourse $P_{1}$ and $P_{2}$ are true.

According to the induction hypothesis, we assume $P_{n}$ is true.

Let $(1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n})= \rho$

and
$1+a_{1} + a_{2}+...+ a_{n} = S$

We have $\rho \geq S$

Okay moving on ...

We have to show this is true and $P_{n} implies P_{n+1}$
$\rho \cdot(1+ a_{n+1} )\geq S + a_{n+1}$

Doing some algebra we get

$\rho \geq S + a_{n+1}(1-\rho)$ which is true because $(1-\rho)\geq 0$ and $\rho \geq S$ and $a_{n+1}\geq 0$

Is this proof correct and is there a more clever way of doing this É

Thanks a lot this is a more clever way of doing it. Thanks again.

But is my way correct É ( My keyboard is acting up)

I think it is correct...I think it will be simple enough......
Actually, induction is not necessary. You can prove it just by multiplying the left side,(1+a1)...(1+an)=1+a1+...an+T,where obviously T>0

**justchillin** · August 14th, 2009, 08:49 AM

Okay thanks.

If anyone has any other suggestions or thinks what i did is too elaborate or wrong please feel free to let me know.

Btw i did make a mistake i said $(1-\rho) \geq 0$ which is false it should have been $(1-\rho)\leq 0$ .

Math Help Forum: Induction proof

LinkBack

Thread Tools

Display

Induction proof

Another one- Can someone help me check this

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)