# Proof by induction

1. Oct 15, 2007

### ar6

1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

First I have to show that P(1) is true
|a1| ≤ |a1| This is true

Assume above is true for all n.

Show that

|∑i=1n+1 ai| ≤ n+1∑i=1 |ai|

|a1 + a2 + a3…+ an + an+1| ≤ |a1| + |a2| + |a3| +…+ |an| + |an+1|

|∑i=1n ai + an+1| ≤ n+1∑i=1 |ai| + |an+1|

assuming I'm on the right track. How can i proceed. This problem is so abstract its driving me crazy. Sorry for formatting.

2. Oct 16, 2007

### MalayInd

you have to arrive at the last equation using the preceding equation.
|a1 + a2 + a3…+ an + an+1|≤|a1 + a2 + a3…+ an |+ |an+1|
....................................{ since it is valid for n=2}
|a1 + a2 + a3…+ an + an+1|≤|a1| + |a2 |+ |a3|+…+ |an |+ |an+1|
.....................................{since valid for n=n(seond last equation i your post)}

Keep Smiling
Malay

3. Oct 16, 2007

### ZioX

You use a strong induction. Assume true for all k<n. Then

$$\left|\sum_i a_i\right|=\left|\sum_{i=1}^{n-1}a_i +a_n\right|$$

You should see where to go from here.

Problems like these are often trivial inductions. Like, for example, showing that taking the intersection of two open sets is open immediately implies that the finite intersection of open sets is always open. Why? Well, for n=3 we have (A n B)nC but we showed AnB is open! So we just repeatedly use this fact.

It's the same thing here, really.

Edit: If you know nothing about open sets, completely disregard.

Last edited: Oct 16, 2007
4. Oct 16, 2007

### learningphysics

You should demonstrate that it is true for n = 2...

MalayInd showed the main inductive step which is valid for n+1>2 but not for n+1 = 2.

5. Oct 16, 2007

### MalayInd

for n+1=2, it reduces to triangle inequality.