1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: General associativity proof

  1. Apr 26, 2013 #1
    1. The problem statement, all variables and given/known data

    I'm inspecting a proof which can be found here: http://unafold.math.rpi.edu/Teaching/MATH-2800/Binary_Ops.pdf

    My question regards the line: (a1...ak-1)*(ak...an) = (a1...ak-1)*((ak...an-1)*an) on the second page of the document.

    Is this true (that is, the ability to group terms k through n on the RHS of the equality, as written) because "any bracketing of a1*a2*...an-1 equals the standard form..."? In other words, I am asking if the inductive hypothesis applies to any qualifying number of summands, regardless of whether they are the same terms as those explicitly expressed in the hypothesis.

    Also, wouldn't this necessarily imply that 1 < k in the second inequality involving k? This may at first seem trivial, but I suppose you'd need fewer than n elements in the right-hand paranthetical expression for this step to hold, which it obviously wouldn't if k = 0.

    2. Relevant equations

    3. The attempt at a solution
    Last edited: Apr 26, 2013
  2. jcsd
  3. Apr 26, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For each positive integer n, let P(n) be the statement "every product with n factors or less, is equal to its standard form". We want to prove P(n) for all positive integers n. Our strategy is to prove the following two statements:

    1. P(3).
    2. For all positive integers n such that n≥4, if P(n-1) then P(n).

    What you're asking about is part of step 2, so we have assumed that P(n-1) holds, and we're working with an arbitrary product of n factors. The step you're asking about changes the bracketing of the product ##a_k\cdots a_n##, which has n-k+1 factors. So it's allowed by assumption, if ##n-k+1\leq n-1##. This inequality is equivalent to ##k\geq 2##. This is true unless all the left brackets are to the left of ##a_1##.
  4. Apr 26, 2013 #3
    Precisely what I thought, thank you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted