- #1
Bob3141592
- 236
- 2
I know this is nothing new to most people here, but my question is really more about the notation than the mathematics. And since this question is really about notation, and it’s my first use of the LaTex equation formatter, I get to experiment with something new. That’s always fun.
But first, a little background. I was playing around with ways to generated ordered list of subsets of a given set, and collected the subsets by size. For a set of size n, there is one null set, and there are n subsets of size one, and of subsets of two elements there are \frac{n!}{2!(n-2)!} or \binom{n}{2} or “n choose 2” subsets, and so on, and if all these are added up there is a total of 2^n subsets for a set of n elements. There are always 2^n subsets of a set on n elements.
It’s well known that \binom{n}{m} are also the binomial coefficients, since
(a+b)^n = \sum_{m=0}^n a^{(n-m)}\binom{n}{m} b^m
and if a = b = 1, and since 1 to any power is still just 1, then we have
2^n = \sum_{m=0}^n \binom{n}{m}
So, what would 3^n look like? We use the formula immediately above with a=1 and b=2 to get
\sum_{m=0}^n 1^{(n-m)} \binom{n}{m} 2^m
But 2^m was given as the original summation above, so we can write
3^n = \sum_{m=0}^n \left( \binom{n}{m} \cdot \sum_{p=0}^m \binom{m}{p} \right)
I liked that, because we can write an equivalent form for 3^n in which the value “3” never appears.
We can do the same thing for 4^n and so on, and in general (and I do hope I can use LaTex to make this come out right)
X^n = \underbrace{\sum_{m=0}^n \left( \binom{n}{m} \cdot \left( \sum_{p=0}^m \binom{m}{p} \cdot \left( \sum_{q=0}^p \binom{p}{q} \cdot \left( \sum_{r=0}^q \binom{q}{r} \cdot \cdot \cdot \cdot \binom{v}{w} \right) \right) \right) \right) \cdot \cdot \cdot}
I think that’s cool, although the notation is awkward. {And even LaTex, though it does have an \underbrace statement, doesn’t let me specify the number of times to repeat the operation, and lining it up in plain text was impossible)
So there must be a better way, and the whole process looks like it’s a perfect candidate for recursion. All we need to use are subscripted variables to control the summations instead of the awkward n, m, p, q, r … form. Let’s see if LaTex can handle this rewrite, as
X^n = \underbrace{\sum_{a_1=0}^n \binom{n}{a_1} \cdot \left( \sum_{a_2=0}^{a_1} \binom{a_1}{a_2} \cdot \left( \sum_{a_3=0}^{a_2} \binom{a_2}{a_3} \cdot \left( \sum_{a_4=0}^{a_3} \binom{a_3}{a_4} \cdot \cdot \cdot \cdot \binom{a_{X-2}}{a_{X-1}} \right) \right) \right) \cdot \cdot \cdot}
Drats, on my screen the typesetting is truncated. The last part is \binom{a_{X-2}}{a_{X-1}}
That’s better, but it still isn’t tidy. Is there a better way? And that’s really my question. Is there a convenient notation to indicate such recursive processes? If anyone knows of it and can inform me, I’d really appreciate it.
If not, I’m suggesting such a notation, and I‘d like your input on it. Now I’m really hoping LaTex can display it as I intend to—but I won’t know until I post it to see if I got it right. So I’ll have to take a look and post a follow up (or edit this post to correct it until I get it right, something else I haven’t done yet as a newbie). Okay, here it is:
X^n = ^{{^*}X [a_0=n]} \sum_{a_{(*+1)}=0}^{a_*} \left( \binom{a_*}{a_{(*+1)}} \cdot * \right)
There, nice and concise, neat. Does that make sense?
The prefacing superscript * designates the recursion structure, and the following value gives the recursion count, or it could be a criteria like n=1, whatever might apply, such as the initial value for a_0 as used.
So what do you think of my suggested notation? Does it seem understandable, simple and usable? Flexible and adaptable? Does it not interfere with any other established use for such notation? Can it be improved?
And for those who enjoy recursion as much as I do, keep in mind that
\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}
So that the entire exponentiation process can be reduced recursively to a series of additions and simple multiplications and nothing more. No factorials, no divisions at all. Granted, it’s going to be a whole lot of additions, but it’s the principle of the thing that matters, right?
But first, a little background. I was playing around with ways to generated ordered list of subsets of a given set, and collected the subsets by size. For a set of size n, there is one null set, and there are n subsets of size one, and of subsets of two elements there are \frac{n!}{2!(n-2)!} or \binom{n}{2} or “n choose 2” subsets, and so on, and if all these are added up there is a total of 2^n subsets for a set of n elements. There are always 2^n subsets of a set on n elements.
It’s well known that \binom{n}{m} are also the binomial coefficients, since
(a+b)^n = \sum_{m=0}^n a^{(n-m)}\binom{n}{m} b^m
and if a = b = 1, and since 1 to any power is still just 1, then we have
2^n = \sum_{m=0}^n \binom{n}{m}
So, what would 3^n look like? We use the formula immediately above with a=1 and b=2 to get
\sum_{m=0}^n 1^{(n-m)} \binom{n}{m} 2^m
But 2^m was given as the original summation above, so we can write
3^n = \sum_{m=0}^n \left( \binom{n}{m} \cdot \sum_{p=0}^m \binom{m}{p} \right)
I liked that, because we can write an equivalent form for 3^n in which the value “3” never appears.
We can do the same thing for 4^n and so on, and in general (and I do hope I can use LaTex to make this come out right)
X^n = \underbrace{\sum_{m=0}^n \left( \binom{n}{m} \cdot \left( \sum_{p=0}^m \binom{m}{p} \cdot \left( \sum_{q=0}^p \binom{p}{q} \cdot \left( \sum_{r=0}^q \binom{q}{r} \cdot \cdot \cdot \cdot \binom{v}{w} \right) \right) \right) \right) \cdot \cdot \cdot}
I think that’s cool, although the notation is awkward. {And even LaTex, though it does have an \underbrace statement, doesn’t let me specify the number of times to repeat the operation, and lining it up in plain text was impossible)
So there must be a better way, and the whole process looks like it’s a perfect candidate for recursion. All we need to use are subscripted variables to control the summations instead of the awkward n, m, p, q, r … form. Let’s see if LaTex can handle this rewrite, as
X^n = \underbrace{\sum_{a_1=0}^n \binom{n}{a_1} \cdot \left( \sum_{a_2=0}^{a_1} \binom{a_1}{a_2} \cdot \left( \sum_{a_3=0}^{a_2} \binom{a_2}{a_3} \cdot \left( \sum_{a_4=0}^{a_3} \binom{a_3}{a_4} \cdot \cdot \cdot \cdot \binom{a_{X-2}}{a_{X-1}} \right) \right) \right) \cdot \cdot \cdot}
Drats, on my screen the typesetting is truncated. The last part is \binom{a_{X-2}}{a_{X-1}}
That’s better, but it still isn’t tidy. Is there a better way? And that’s really my question. Is there a convenient notation to indicate such recursive processes? If anyone knows of it and can inform me, I’d really appreciate it.
If not, I’m suggesting such a notation, and I‘d like your input on it. Now I’m really hoping LaTex can display it as I intend to—but I won’t know until I post it to see if I got it right. So I’ll have to take a look and post a follow up (or edit this post to correct it until I get it right, something else I haven’t done yet as a newbie). Okay, here it is:
X^n = ^{{^*}X [a_0=n]} \sum_{a_{(*+1)}=0}^{a_*} \left( \binom{a_*}{a_{(*+1)}} \cdot * \right)
There, nice and concise, neat. Does that make sense?
The prefacing superscript * designates the recursion structure, and the following value gives the recursion count, or it could be a criteria like n=1, whatever might apply, such as the initial value for a_0 as used.
So what do you think of my suggested notation? Does it seem understandable, simple and usable? Flexible and adaptable? Does it not interfere with any other established use for such notation? Can it be improved?
And for those who enjoy recursion as much as I do, keep in mind that
\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}
So that the entire exponentiation process can be reduced recursively to a series of additions and simple multiplications and nothing more. No factorials, no divisions at all. Granted, it’s going to be a whole lot of additions, but it’s the principle of the thing that matters, right?
Last edited: