• Support PF! Buy your school textbooks, materials and every day products via PF Here!

General associativity proof

  • Thread starter Syrus
  • Start date
214
0
1. Homework Statement

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



3. The Attempt at a Solution
 
Last edited:

Fredrik

Staff Emeritus
Science Advisor
Gold Member
10,730
404
1. Homework Statement

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



3. The Attempt at a Solution
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##.
 
214
0
Precisely what I thought, thank you.
 

Want to reply to this thread?

"General associativity proof" You must log in or register to reply here.

Related Threads for: General associativity proof

  • Posted
Replies
6
Views
4K
  • Posted
Replies
4
Views
2K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
3
Views
1K
  • Posted
Replies
2
Views
762
  • Posted
Replies
7
Views
3K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
1
Views
5K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top