Thread: proving associative property of any two vectors

Problem:Prove that any two ways of associating a sum of any number of vectors give the same sum. (Hint. Use induction on the number of vectors.)

Proof: Base Case: Let there be three vectors namely v₁,v₂,v₃. We see that (v₁₊v₂)₊v₃₌v₁₊(v₂₊v₃).


Inductive Case: Let k be the number of vectors where k∈N. We want to assume that for v_1...v_kthat we could associate them any two ways and get the same sum. We want to show for k+1 vectors that the same thing holds.

Case 1: Odd number of k+1 vectors
( (v₁₊v₂)+...+(v_k-1+v_k))+v_k+1 =(v₁₊ (v₂₊v₃)+...+(v_k+V_k+1))=v1+ ((v₂₊v₃)+...+(v_k+V_k+1))

Case 2: Even Number of k+1 vectors
((v₁₊v₂)+...+(v_k-2+v_k-1)+v_k)+v_k+1=(v₁+(v₂+v₃)+..+(v_k-1+v_k))+v_k+1=(v₁+v₂)+...+(v_k+v_k+1)=v₁+((v₂+v₃)+..+(v_k+v_k+1))

Hence by induction it holds for k+1 vectors.

Did I do it correctly?

you've only shown 3 out of the many, many cases for k odd, and 4 cases for k even. this particular proof is a pain, because the number of cases grows rapidly as k does.

let's say S is a sum (associated arbitrarily) of k+1 vectors. we want to show that S = ((...(v₁+v₂)+v₃)+...+v_k)+v_k+1. we will assume this is true for any sum of j vectors with: 3 ≤ j ≤ k.

we can write:

S = A+B, for two sums A and B, and the largest either A or B can be is a sum of k vectors.

applying our induction hypothesis to B we have:

B = ((...(v_j+v_j+1)+v_j+2)+...+v_k)+v_k+1, for some v_j.

applying our induction hypothesis to A, we have:

A = ((...(v₁+v₂)+v₃)+...+v_j-2)+v_j-1.

if we let C = ((...(v_j+v_j+1)+...+v_k-2)+v_k,

we have A+B = A+(C+v_k+1) = (A+C)+v_k+1.

applying the induction hypothesis to A+C, we have:

A+C = ((...(v₁+v₂)+v₃+...+v_k-1)+v_k,

hence S = (A+C)+v_k+1 = ((...(v₁+v₂)+v₃)+...+v_k)+v_k+1, as desired.

(the problem with your proof is that association can occur with more than "adjacent pairs", you can have sums like:

((v₁+v₂)+v₃)+(v₄+v₅) or

(v₁+(v₂+v₃)+v₄)+v₅ and so on).

oh ok thanks. this makes alot of sense now. i didn't even think of that.