# Thread: Induction proof

1. ## Induction proof

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

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?

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

3. ## Another one- Can someone help me check this

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

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

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

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

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

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