- #1

- 1,462

- 44

- I
- Thread starter Mr Davis 97
- Start date

- #1

- 1,462

- 44

- #2

fresh_42

Mentor

- 14,358

- 11,671

It would help to see all the steps. Otherwise we can only repeat the proof.

We start with ##a_1(a_2a_3)=(a_1a_2)a_3##. Now how is the statement worded? ##a_1\ldots a_n## doesn't exist, yet.

- #3

- 1,462

- 44

It says after proving the trivial base cases, suppose that for any ##k < n## that any bracketing of the product of ##k## elements can be reduced without altering the value to an expression of the form ##b_1 \cdot (b_2 \cdot (b_3 \cdot ( \cdots \cdot b_k)) \dots)##. Given this assumption we are supposed to argue that any bracketing of ##n## elements must break into two subproducts so that we can apply the induction assumption to each subproduct.It would help to see all the steps. Otherwise we can only repeat the proof.

We start with ##a_1(a_2a_3)=(a_1a_2)a_3##. Now how is the statement worded? ##a_1\ldots a_n## doesn't exist, yet.

My problem is that I don't know how the breaking into two subproducts given any bracketing of ##n## elements in justified.

- #4

fresh_42

Mentor

- 14,358

- 11,671

So this is the induction hypothesis:It says after proving the trivial base cases, suppose that for any ##k < n## that any bracketing of the product of ##k## elements can be reduced without altering the value to an expression of the form ##b_1 \cdot (b_2 \cdot (b_3 \cdot ( \cdots \cdot b_k)) \dots)##. Given this assumption we are supposed to argue that any bracketing of ##n## elements must break into two subproducts so that we can apply the induction assumption to each subproduct.

My problem is that I don't know how the breaking into two subproducts given any bracketing of ##n## elements in justified.

Suppose that

Now we have to prove:

Suppose that

It is part of our IF clause. We have some given bracketing of ##n## elements. In case it is of the form ##a_1(a_2(\ldots a_n)\ldots )## we are done. All other cases are of the form ##(a_1 \ldots a_k)(a_{k+1}\ldots a_n)## with some bracketing of the two parts and ##1<k##. I assume we have commutativity, too, so we may assume ##k<n-1##, too. For the non commutative case, the expression ##a_1\ldots a_n## has to be explained, as e.g. in the case of functions. It is sloppy to write ##fg## and not mentioning whether ##g(f(x))## or ##f(g(x))## is meant. It's usually the latter, but purists prefer the first version.

- Last Post

- Replies
- 6

- Views
- 4K

- Last Post

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 20

- Views
- 4K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 5K

- Last Post

- Replies
- 2

- Views
- 4K

- Last Post

- Replies
- 10

- Views
- 3K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 7K

- Last Post

- Replies
- 5

- Views
- 3K