Notation for recursion - better typesetting

In summary, the conversation focused on the use of LaTex notation to express recursive processes and how it can be used to simplify mathematical equations. The speaker also shared their own suggested notation for recursive processes and asked for feedback on its usability. The potential for reducing complex exponentiation processes to simple additions and multiplications was also discussed.
  • #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 [itex]\frac{n!}{2!(n-2)!}[/itex] or [itex]\binom{n}{2}[/itex] or “n choose 2” subsets, and so on, and if all these are added up there is a total of [itex]2^n[/itex] subsets for a set of n elements. There are always [itex]2^n[/itex] subsets of a set on n elements.

It’s well known that [itex]\binom{n}{m}[/itex] are also the binomial coefficients, since
[tex](a+b)^n = \sum_{m=0}^n a^{(n-m)}\binom{n}{m} b^m[/tex]
and if a = b = 1, and since 1 to any power is still just 1, then we have
[tex]2^n = \sum_{m=0}^n \binom{n}{m}[/tex]

So, what would [itex]3^n[/itex] look like? We use the formula immediately above with a=1 and b=2 to get

[tex]\sum_{m=0}^n 1^{(n-m)} \binom{n}{m} 2^m[/tex]

But [itex]2^m[/itex] was given as the original summation above, so we can write

[tex]3^n = \sum_{m=0}^n \left( \binom{n}{m} \cdot \sum_{p=0}^m \binom{m}{p} \right)[/tex]

I liked that, because we can write an equivalent form for [itex]3^n[/itex] in which the value “3” never appears.

We can do the same thing for [itex]4^n[/itex] and so on, and in general (and I do hope I can use LaTex to make this come out right)

[tex]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} [/tex]

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

[tex]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}[/tex]

Drats, on my screen the typesetting is truncated. The last part is [itex] \binom{a_{X-2}}{a_{X-1}}[/itex]

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:

[tex]X^n = ^{{^*}X [a_0=n]} \sum_{a_{(*+1)}=0}^{a_*} \left( \binom{a_*}{a_{(*+1)}} \cdot * \right)[/tex]

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 [itex]a_0[/itex] 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

[tex]\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}[/tex]

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:
Mathematics news on Phys.org
  • #2
Bob3141592 said:
There, nice and concise, neat. Does that make sense?
I don't think so. It is a monster sum of sums and an abbreviation doesn't change this. I think all iterative constructions which are of some use somewhere have already been investigated in the history of mathematics. Especially as we now have computers, the need for them diminishes daily. In forme times, without computers, people were much more forced to use such constructions, e.g. continued fractions.
 

1. What is recursion notation?

Recursion notation is a mathematical notation that represents a repeated process or function in a concise and structured way. It is commonly used in computer science and mathematics to describe algorithms and functions that call themselves.

2. How is recursion notation different from regular mathematical notation?

Unlike regular mathematical notation, recursion notation specifically focuses on representing a repeated process or function. It often uses symbols such as "n" or "k" to represent the number of times the process or function is repeated, and it may also include specific instructions or rules for each iteration.

3. What are some common symbols used in recursion notation?

Some common symbols used in recursion notation include the factorial symbol (!), summation symbol (∑), product symbol (∏), and the ellipsis symbol (...). These symbols are used to represent repeated operations or functions in a concise and easy-to-understand way.

4. How is recursion notation typically typeset or formatted?

Recursion notation is typically typeset in a structured and hierarchical manner, with each iteration or function call being indented or nested within the previous one. Some common typesetting conventions for recursion notation include using different font styles or sizes to distinguish between different levels of recursion, and using brackets or parentheses to group together related operations.

5. Why is better typesetting important for recursion notation?

Better typesetting for recursion notation can help clarify and make the notation more readable and understandable. Since recursion notation can often involve multiple levels of nested operations, using consistent and clear typesetting can make it easier to follow the logic and steps of the recursion. It also allows for easier identification of any errors or mistakes in the notation.

Similar threads

Replies
1
Views
766
  • General Math
Replies
9
Views
1K
Replies
20
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • General Math
Replies
0
Views
798
  • General Math
Replies
4
Views
2K
Replies
6
Views
885
Replies
3
Views
621
Replies
15
Views
1K
  • General Math
Replies
2
Views
1K
Back
Top